1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
|
#include<iostream> #include<queue> #include<map> #include<string> #define MIN(a,b) ((a)<(b)?(a):(b)) #define N 201 using namespace std;
int adjM[N][N] = {}; int (int n, int st, int end); int main() { int n, r, i, j, Case = 1;
while (scanf("%d%d", &n, &r) && n) { map<string, int> city; string str1, str2; int count = 0, a, b, w; for (i = 0; i <= n; i++) for (j = 0; j <= n; j++) adjM[i][j] = 0;
for (i = 0; i < r; i++) { cin >> str1 >> str2 >> w; if (!city.count(str1)) city[str1] = ++count; if (!city.count(str2)) city[str2] = ++count;
a = city[str1]; b = city[str2];
adjM[b][a] = adjM[a][b] = w; }
cin >> str1 >> str2; printf("Scenario #%dn", Case++); printf("%d tonsnn", SPFA(n, city[str1], city[str2])); }
return 0; } int (int n, int st, int end) { queue<int> Q; int weight[N] = {}; bool inQ[N] = {}; Q.push(st);
while (!Q.empty()) { int u = Q.front(); Q.pop(); inQ[u] = false;
for (int v = 1; v <= n; v++) if (adjM[u][v]) { int maxW = weight[u] ? MIN(adjM[u][v], weight[u]) : adjM[u][v];
if (maxW > weight[v]) { weight[v] = maxW; if (!inQ[v]) { Q.push(v); inQ[v] = true; } } } }
return weight[end]; }
|
近期评论