题目：http://poj.org/problem?id=3463
当然要给一个点记最短路和次短路的长度和方案。
但往优先队列里放的结构体和vis竟然也要区分0/1，就像把一个点拆成两个点了一样。
不要区分k的fx。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=1005,M=10005; int T,n,m,head[N],xnt,dis[N][2],f[N][2],st,en; bool vis[N][2]; struct Ed{ int next,to,w; Ed(int n=0,int t=0,int z=0):next(n),to(t),w(z) {} }ed[M]; struct Node{ int bh,dis;bool fx; Node(int b=0,int d=0,bool f=0):bh(b),dis(d),fx(f) {} bool operator< (const Node &b)const { return dis>b.dis; } }; void add(int x,int y,int z) { ed[++xnt]=Ed(head[x],y,z);head[x]=xnt; } void dj() { memset(vis,0,sizeof vis);memset(dis,1,sizeof dis); memset(f,0,sizeof f); priority_queue<Node> q; dis[st][0]=0;//dis[st][1] f[st][0]=1;//! q.push(Node(st,0,0));//no push [1] while(q.size()) { Node t=q.top();q.pop();int k=t.bh;bool fx=t.fx; while(q.size()&&vis[k][fx])t=q.top(),q.pop(),k=t.bh,fx=t.fx; if(vis[k][fx])break;vis[k][fx]=1; for(int i=head[k],v;i;i=ed[i].next)//不要区分fx，[k][1]也能更新[v][0]！ { int d=dis[k][fx],w=ed[i].w; if(d+w<dis[v=ed[i].to][0]) { dis[v][1]=dis[v][0];f[v][1]=f[v][0]; dis[v][0]=d+w;f[v][0]=f[k][fx]; q.push(Node(v,dis[v][0],0)); q.push(Node(v,dis[v][1],1));//!because zj's [1] also has been pshp } else if(d+w==dis[v][0]) f[v][0]+=f[k][fx]; else if(d+w<dis[v][1]) { dis[v][1]=d+w;f[v][1]=f[k][fx]; q.push(Node(v,dis[v][1],1)); } else if(d+w==dis[v][1]) f[v][1]+=f[k][fx]; } } } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(head,0,sizeof head);xnt=0; int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z);add(x,y,z); } scanf("%d%d",&st,&en); dj(); if(dis[en][1]==dis[en][0]+1)f[en][0]+=f[en][1]; printf("%d ",f[en][0]); } return 0; }