建圖還是有點煩人的。

#include<map> #include<string> #include<stdio.h> #include<iostream> #include<string.h> #define maxn 105 #define INF 99999999 using namespace std; int g[maxn][maxn],vis[maxn],dis[maxn],n; void init() {int i,j;for(i=0;i<=n;i++)for(j=0;j<=n;j++)if(i==j)g[i][j]=0;else g[i][j]=INF; } void floyd() {int i,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++){if(g[j][k]>g[j][i]+g[i][k])g[j][k]=g[j][i]+g[i][k];} } int main() {int i,j,m,c;string ss,se,start;char cc[20];char item[1005][20];int ff=0;while(scanf("%d%d%d",&n,&c,&m)!=EOF){map<string,int>mp; if(n==0&&c==0&&m==0)break;init();int num=1;cin>>start;mp[start]=num++;for(i=1;i<=c;i++)scanf("%s",item[i]);for(i=0;i<m;i++){cin>>ss; scanf("%s",cc); cin>>se;if(!mp[ss])mp[ss]=num++;if(!mp[se])mp[se]=num++;int len=strlen(cc);int l=0;int fr,ed;ed=len-2;for(fr=2;fr<ed;fr++){l=l*10+cc[fr]-'0';}//printf("%d\n",l);if(cc[0]=='-'){if(g[mp[ss]][mp[se]]>l)g[mp[ss]][mp[se]]=l;}else if(cc[len-1]=='-'){if(g[mp[se]][mp[ss]]>l)g[mp[se]][mp[ss]]=l;}else {if(g[mp[ss]][mp[se]]>l)g[mp[ss]][mp[se]]=l;if(g[mp[se]][mp[ss]]>l)g[mp[se]][mp[ss]]=l;}}floyd();int ans=0;printf("%d. ",++ff);string st;for(i=1;i<=c;i++){st="";int strl=strlen(item[i]);for(j=0;j<strl;j++){st+=item[i][j];}//cout<<st<<endl;ans+=g[mp[start]][mp[st]];ans+=g[mp[st]][mp[start]];}printf("%d\n",ans);} }

?

轉載于:https://www.cnblogs.com/sweat123/p/4682688.html

總結

以上是生活随笔為你收集整理的hdu2923 最短路floyd的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。