次短路与条数
#include <stdio.h> #include <string.h> #define N 10005 #define INF 0x3f3f3f3f struct Edge{ int u,val,next; }e[2*N]; int p[N],vis[N][2],d[N][2],cnt[N][2]; void add(int n,int m) { int i,x,y,cost,cout = 1; for(i = 1 ; i <= n ; i++) p[i] = -1; while(m--) { scanf("%d %d %d",&x,&y,&cost); x++;y++; e[cout].u = y; e[cout].val = cost; e[cout].next = p[x]; p[x] = cout++; } } void dijkstra(int s,int t,int n) { int i,x,y,temp,ok; for(i = 1 ; i <= n ; i++) { d[i][0] = INF; d[i][1] = INF; vis[i][0] = 0; vis[i][1] = 0; } d[s][0] = 0; cnt[s][0] = 1; for(i = 1 ; i <= 2*n ; i++) { temp = INF,ok ,x = -1; for(y = 1 ; y <= n ;y++) if(!vis[y][0]&&temp>d[y][0]) { temp = d[y][0]; ok = 0; x = y; } else if(!vis[y][1]&&temp>d[y][1]) { temp = d[y][1]; ok = 1; x = y; } if(x == -1) break; vis[x][ok] = 1; for(y = p[x] ; y!=-1; y = e[y].next) { int newd = d[x][ok]+e[y].val; int u = e[y].u; if(newd<d[u][0]) { d[u][1] = d[u][0]; d[u][0] = newd; cnt[u][1] = cnt[u][0]; cnt[u][0] = cnt[x][ok]; }else if(newd == d[u][0]){ cnt[u][0] += cnt[x][ok]; }else if(newd<d[u][1]){ d[u][1] = newd; cnt[u][1] = cnt[x][ok]; }else if(newd == d[u][1]){ cnt[u][1]+=cnt[x][ok]; } } } } int main() { int n,m,s,t;; while(~scanf("%d %d",&n,&m)) { scanf("%d %d",&s,&t); s++;t++; add(n,m); dijkstra(s,t,n); printf("%d %d ",d[t][1],cnt[t][1]); } return 0; }