|
参考了下别人的建图方式，自己的建图怎么都不对，还是不太懂为什么非要3层，2层却错
还要注意的就是要用优先队列优化
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=300010;
const int maxm=900010;
const int inf=1<<30;
int e,n,m,c,head[maxn],pnt[maxm],nxt[maxm],cost[maxm],dist[maxn];
bool vis[maxn],exsit[maxn];
struct Point
{
int u;
bool operator <(const Point &a)const
{
return dist[u]>dist[a.u];
}
};
priority_queue<Point> q;
void AddEdge(int u,int v,int c)
{
pnt[e]=v;nxt[e]=head[u];cost[e]=c;head[u]=e++;
}
void Spfa(int st)
{
for(int i=1;i<=3*n;i++)
dist[i]=inf;
dist[st]=0;
Point p;
p.u=st;
q.push(p);
while(!q.empty())
{
Point u=q.top();
q.pop();
vis[u.u]=0;
for(int i=head[u.u];i!=-1;i=nxt[i])
if(dist[pnt[i]]>dist[u.u]+cost[i])
{
dist[pnt[i]]=dist[u.u]+cost[i];
if(!vis[pnt[i]])
{
p.u=pnt[i];
q.push(p);
vis[pnt[i]]=1;
}
}
}
if(dist[n]==inf)
{
printf("-1\n");
return;
}
printf("%d\n",dist[n]);
}
int main()
{
int T,cas=1;
scanf("%d",&T);
while(T--)
{
e=0;
memset(head,-1,sizeof(head));
memset(exsit,0,sizeof(exsit));
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++)
{
int val;
scanf("%d",&val);
AddEdge(i,2*n+val,0);
AddEdge(n+val,i,0);
exsit[val]=1;
}
for(int i=1;i<n;i++)
if(exsit[i]&&exsit[i+1])
{
AddEdge(2*n+i,n+i+1,c);
AddEdge(2*n+i+1,n+i,c);
}
for(int i=0;i<m;i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
AddEdge(u,v,c);
AddEdge(v,u,c);
}
printf("Case #%d: ",cas++);
if(n==0)
{
printf("-1\n");
continue;
}
Spfa(1);
}
return 0;
}
| 
转播
