首页 > 代码库 > hdu 1688
hdu 1688
最短路与次短路条数
#include <stdio.h>#include <string.h>#define N 10005#define INF 0x3f3f3f3fstruct 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); e[cout].u = y; e[cout].val = cost; e[cout].next = p[x]; p[x] = cout++; }}int dijkstra(int s,int t,int n,int m){ 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 num = cnt[t][0]; if(d[t][0] + 1 == d[t][1]) num+=cnt[t][1]; return num;}int main(){ int t,n,m; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); add(n,m); int s,t; scanf("%d %d",&s,&t); int ans = dijkstra(s,t,n,m); printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。