題目描述

N個城市，標(biāo)號從0到N-1，M條道路，第K條道路（K從0開始）的長度為2^K，求編號為0的城市到其他城市的最短距離。

輸入

第一行兩個正整數(shù)N（2<=N<=100）M(M<=500),表示有N個城市，M條道路，
接下來M行兩個整數(shù)，表示相連的兩個城市的編號。

輸出

N-1行，表示0號城市到其他城市的最短路，如果無法到達(dá)，輸出-1，數(shù)值太大的以MOD 100000 的結(jié)果輸出。

樣例輸入

4 3 0 1 1 2 2 0

樣例輸出

1 3 -1

?

#include <iostream> #include <cmath> using namespace std;const int maxn = 100; const int inf = 1000000000;int n, m; //n個城市,m條道路 int G[maxn][maxn]; int d[maxn]; bool vis[maxn] = {false};int length(int i) {return (int)pow(2,i); }void dij(int s) {fill(d, d+maxn, inf);d[s] = 0;for(int i = 0; i < n; i++){int u = -1, min = inf;for(int j = 0; j < n; j++){if(vis[j] == false && d[j] < min){u = j;min = d[j];}}if(u == -1) return;vis[u] = true;for(int v = 0; v < n; v++){if(vis[v] == false && G[u][v] != inf && d[u]+G[u][v] < d[v]){d[v] = (d[u] + G[u][v]);}}} } int main() {scanf("%d%d", &n, &m);fill(G[0], G[0]+maxn*maxn, inf);for(int i = 0; i < m; i++){int a,b;scanf("%d%d", &a, &b);G[a][b] = length(i);G[b][a] = length(i);}dij(0);for(int i = 0; i < n; i++){if(i == n - 1 && d[i] != 0){if(d[i] == inf) printf("-1");else printf("%d", d[i] % 100000);}else{if(d[i] == inf) printf("-1\n");else if(d[i] == 0) continue;else printf("%d\n", d[i] % 100000);}}return 0; }

WA原因：錯誤50%，沒找到原因..

總結(jié)

以上是生活随笔為你收集整理的Codeup-问题 C: 最短路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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