本文主要是介绍1087 All Roads Lead to Rome（最短路求最大权值，最短路路径条数，节点个数，回溯路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
（这题基本上把最短路能求的都求了个遍，除了麻烦一点，难度其实还好）
（卡题原因：dijks漏了对路径条数的初始化。）
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
string st,ed;
map<string,int>mp;
map<int,string>name;
map<int,int>w;
int e[210][210];
int indx=0;
int getID(string s){if(mp.count(s)){return mp[s];}name[indx]=s;mp[s]=indx++;return mp[s];
}
int dist[210];
int hap[210],num[210];
int sum[210];
int p[210];
bool vis[210];
void dijks(int u){memset(dist,0x3f,sizeof dist);memset(vis,0,sizeof vis);memset(p,-1,sizeof p);dist[u]=0;sum[u]=1;//记得每个都要初始化，漏了这个，结果debug半多小时for(int i=0;i<indx;i++){u=-1;int mi=INT_MAX;for(int j=0;j<indx;j++){if(!vis[j]&&mi>dist[j]){u=j;mi=dist[j];}}if(u==-1)break;vis[u]=1;for(int j=0;j<indx;j++){if(!vis[j]){if(dist[j]==dist[u]+e[u][j]){sum[j]=sum[u]+sum[j];if(hap[j]==hap[u]+w[j]){if(num[j]>num[u]+1){p[j]=u;num[j]=num[u]+1;}}else if(hap[j]<hap[u]+w[j]){p[j]=u;hap[j]=hap[u]+w[j];num[j]=num[u]+1;}}else if(dist[j]>dist[u]+e[u][j]){sum[j]=sum[u];p[j]=u;dist[j]=dist[u]+e[u][j];hap[j]=hap[u]+w[j];num[j]=num[u]+1;}}}}u=getID(ed);cout<<sum[u]<<' '<<dist[u]<<' '<<hap[u]<<' '<<(hap[u])/num[u]<<endl;
}
int flag=0;
void dfs(int u){if(u==-1)return ;dfs(p[u]);if(flag)cout<<"->";cout<<name[u];flag=1;
}
signed main(){cin>>n>>k>>st;memset(e,0x3f,sizeof e);ed="ROM";getID(st);getID(ed);for(int i=0;i<n-1;i++){string city;cin>>city;int d;cin>>d;w[getID(city)]=d;// cout<<getID(city)<<' ';}w[getID(st)]=0;for(int i=0;i<k;i++){string c1,c2;cin>>c1>>c2;int a,b,d;cin>>d;a=getID(c1);b=getID(c2);e[a][b]=e[b][a]=d;}dijks(getID(st));dfs(getID(ed));
}这篇关于1087 All Roads Lead to Rome（最短路求最大权值，最短路路径条数，节点个数，回溯路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
