本文共 2587 字，大约阅读时间需要 8 分钟。
普通版：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long#define mod 1000000007#define mod1 10001#define mem(a) memset(a,0,sizeof(a))using namespace std;const int maxn = 100 + 5 , inf = 0x3f3f3f3f ;int m,n,G[maxn][maxn],d[maxn],f[maxn],vis[maxn];void Init(){ for(int i = 1 ; i <= n ; i++ ) for(int j = 1 ; j <= n ; j ++ ){ if(i==j) G[i][j] = 0; else G[i][j] = inf; }}void dijkstra(int u){ mem(vis); for(int i = 1 ; i <=n ; i ++ ) d[i] = inf; d[u] = 0; for(int i = 1 ; i <= n ; i ++ ){ int minn = inf; int pos = 0; for(int j = 1 ; j <= n ; j ++ ){ if(!vis[j]&&minn>d[j]){ pos = j ; minn = d[j]; } } vis[pos] = 1; for(int j = 1 ; j <=n ; j ++ ){ if(d[j]>d[pos]+G[pos][j]&&G[pos][j]!=inf){ d[j] = d[pos] + G[pos][j]; f[j] = pos; } } }}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); while(scanf("%d",&n)!=EOF){ Init(); for(int i = 2 ; i<=n ; i ++ ){ for(int j = 1 ; j < i ; j ++ ){ char s[10]; scanf("%s",s); if(s[0]!='x') G[i][j] = G[j][i] = atoi(s); } } dijkstra(1); int ans = -1; for(int i=2;i<=n;i++) ans = max(ans,d[i]); printf("%d\n",ans); }}
队列优化版：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long#define mod 1000000007#define mod1 10001#define mem(a) memset(a,0,sizeof(a))using namespace std;typedef pair pii;const int maxn = 100 + 5 , inf = 0x3f3f3f3f ;int m,n,G[maxn][maxn],d[maxn],f[maxn],vis[maxn];void Init(){ for(int i = 1 ; i <= n ; i++ ) for(int j = 1 ; j <= n ; j ++ ){ if(i==j) G[i][j] = 0; else G[i][j] = inf; }}void dijkstra(int qp){ for(int i = 1 ; i <= n ; i ++ ) d[i] = inf; d[qp] = 0; priority_queue ,greater >q; q.push(pii(d[qp],qp)); mem(vis); while(!q.empty()){ pii now = q.top(); q.pop(); int u = now.second; if(vis[u]) continue; vis[u] = 1; for(int i = 1 ; i <= n ; i ++ ){ if(d[i] > d[u] + G[u][i] && G[u][i] != inf){ f[i] = u; d[i] = d[u] + G[u][i]; q.push(pii(d[i],i)); } } }}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); while(scanf("%d",&n)!=EOF){ Init(); for(int i = 2 ; i<=n ; i ++ ){ for(int j = 1 ; j < i ; j ++ ){ char s[10]; scanf("%s",s); if(s[0]!='x') G[i][j] = G[j][i] = atoi(s); } } dijkstra(1); int ans = -1; for(int i=2;i<=n;i++) ans = max(ans,d[i]); printf("%d\n",ans); }}
转载于:https://www.cnblogs.com/seven7777777/p/10278721.html