最短路問題，要求出最短路的個(gè)數(shù)。

輸出一條得到JavaBean最多的最短路徑

?

#include<stdio.h> #include<string.h> #define inf 0x3fffffff int n,m,map[510][510],dp[510],mark[510],dis[510],w[510],pre[510],link[510]; int st,ed; void dijkstra() {int i,j,k,min;memset(mark,0,sizeof(mark));//標(biāo)記房間是否走過memset(dp,0,sizeof(dp));//記錄到達(dá)位置得到最多的JavaBeanmemset(pre,-1,sizeof(pre));//記錄到達(dá)此房間的前一個(gè)房間memset(link,0,sizeof(link));//記錄到達(dá)此位置最短路的個(gè)數(shù)for(i=0;i<n;i++)dis[i]=inf;//距離起點(diǎn)的最短距離dis[st]=0;link[st]=1;dp[st]=w[st];for(i=0;i<n;i++){min=inf;k=-1;for(j=0;j<n;j++){if(!mark[j]&&min>dis[j]){min=dis[j];k=j;}}mark[k]=1;for(j=0;j<n;j++){if(mark[j]||dis[j]<dis[k]+map[k][j]||map[k][j]==inf)continue;if(dis[j]==dis[k]+map[k][j])//如果從k到達(dá)j的距離與j的最小距離相等link[j]+=link[k];//j的最短路數(shù)要加上k的else link[j]=link[k];//如果從k到達(dá)j的路短的話，到達(dá)j的最短路數(shù)就等于k的最短路數(shù)if(dis[j]>dis[k]+map[k][j]||dp[j]<dp[k]+w[j])//路徑更短或者路勁相等得到的JavaBean更多{ dis[j]=dis[k]+map[k][j];pre[j]=k;dp[j]=dp[k]+w[j];} }} } void prit(int u) {if(u==st){printf("%d",st);return;}prit(pre[u]);printf(" %d",u); } int main() {int i,j,x,y,p;while(scanf("%d%d%d%d",&n,&m,&st,&ed)!=-1){for(i=0;i<n;i++)for(j=0;j<n;j++)map[i][j]=inf;for(i=0;i<n;i++)scanf("%d",&w[i]);for(i=0;i<m;i++){scanf("%d%d%d",&x,&y,&p);if(map[x][y]>p)map[x][y]=map[y][x]=p;}dijkstra();printf("%d %d\n",link[ed],dp[ed]);prit(ed);printf("\n");}return 0; }

?

5 10 0 2
1 2 1 5 3
0 1 2
0 2 4
0 3 3
0 4 1
1 2 2
1 3 1
1 4 1
2 3 1
2 4 3
3 4 2

?

轉(zhuǎn)載于:https://www.cnblogs.com/dyllove98/archive/2013/06/06/3122847.html

總結(jié)

以上是生活随笔為你收集整理的zoj 2526的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。