测试题目： POJ3255
///求次短路 ///使用优先队列Dijkstra算法 ///复杂度O(ElogV) ///注意初始化 ///dist2[v]=min(dist[u]+e(u,v),dist2[u]+e(u,v)) #include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<cstring> #include<string> #include<set> #include<queue> #include<fstream> using namespace std; typedef pair<int,int> PII; const int MAXN=1e4+5; const int MAXM=2e5+5; const int INF=0x3f3f3f3f; int dist[MAXN],head[MAXN],tot; int dist2[MAXN];//次短距离 int pre[MAXN]; struct Edge { int from,to,cost,nxt; Edge(){} Edge(int _from,int _to,int _cost):from(_from),to(_to),cost(_cost){} }e[MAXM]; void addedge(int u,int v,int w) { e[tot].from=u;e[tot].to=v;e[tot].cost=w; e[tot].nxt=head[u];head[u]=tot++; } struct qnode { int c,v; qnode(int _c=0,int _v=0):c(_c),v(_v){} bool operator < (const qnode &rhs) const {return c>rhs.c;} }; void Dijkstra(int n,int st)//点的编号从1开始 { for(int i=0;i<=n;i++) dist[i]=INF,dist2[i]=INF; priority_queue<qnode> pq; while(!pq.empty()) pq.pop(); dist[st]=0; pq.push(qnode(0,st)); qnode frt; while(!pq.empty()) { frt=pq.top(); pq.pop(); int u=frt.v,d=frt.c; if(dist2[u]<d) continue; for(int i=head[u];i!=-1;i=e[i].nxt) { int to=e[i].to; int cost=e[i].cost; int d2=d+cost; if(dist[to]>d2) { swap(dist[to],d2); pre[to]=u; pq.push(qnode(dist[to],to)); } if(dist2[to]>d2&&dist[to]<d2) { dist2[to]=d2; pq.push(qnode(dist2[to],to)); } } } } int main() { int vN,eN; while(scanf("%d%d",&vN,&eN)!=EOF) { tot=0;memset(head,-1,sizeof(head)); int u,v,w; for(int i=1;i<=eN;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w);addedge(v,u,w); } int st,ed; st=1,ed=vN; //scanf("%d%d",&st,&ed); //if(st==ed) {printf("0\n");continue;} Dijkstra(vN,st); // for(int i=0;i<=vN-1;i++) // printf("%d ",dist[i]); // printf("\n"); // for(int i=0;i<=vN-1;i++) // printf("%d ",pre[i]); // printf("\n"); printf("%d\n",dist2[ed]); } return 0; } /* 4 6 1 2 1 1 2 5 1 3 2 2 3 2 2 4 1 2 4 6 ans:4 */