这题让我第一次感受到了什么叫做在绝望中A题。这题我总共交了18次，TLE不知道几次，WA也不知道几次。
这题不能用dijkstra，用这个我一直超时（我没试过dij+优先队列优化，好像优先队列优化后可以过).。
用了我近一天的时间。。。。。。
#include<stdio.h> #include<queue> #include<string.h> using namespace std; #define maxn 1002 #define INF 99999999 struct node { int from; int to; int val; int flag;//标记该条边能否使用 int next; }a[2*50005]; int index,head[maxn],pre[maxn],n,m,ret,dis[maxn],vis[maxn],mark[maxn];//mark[]用来保存路径的位置 //pre[]来保存路径 void add(int x,int y,int z) { a[index].from=x; a[index].to=y; a[index].val=z; a[index].flag=1;//初始都能使用 a[index].next=head[x]; head[x]=index++; } void spfa() { int i,j,pos; memset(vis,0,sizeof(vis)); queue<int>q; for(i=1;i<=n;i++) dis[i]=INF; dis[1]=0; vis[1]=1; q.push(1); while(!q.empty()) { int cur=q.front(); q.pop(); vis[cur]=0; for(i=head[cur];i!=-1;i=a[i].next) { int v=a[i].to; if(a[i].flag&&dis[v]>dis[cur]+a[i].val)//a[].flag标记是否使用 { if(!ret){//ret表示这是第几次spfa,如果第一次，那要记录路径 pre[v]=cur;//保存当前点的前一个点 mark[v]=i;//保存当前点的位置 } dis[v]=dis[cur]+a[i].val; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } int main() { int i,j,t,ans; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); index=1; memset(head,-1,sizeof(head)); for(i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } memset(pre,-1,sizeof(pre)); ret=0; spfa(); ret=1; ans=0; for(i=n;i!=-1;i=pre[i]) { a[mark[i]].flag=0;//i这里表示点，mark[i]表示点i的位置，a[mark[i]].flag表示点i不能使用 spfa(); if(dis[n]>ans) { ans=dis[n]; } a[mark[i]].flag=1; } if(ans>=INF)printf("-1 "); else printf("%d ",ans); } }