hdu 2112 HDU Today（映射+spfa）

HDU Today

Time Limit: 15000/5000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3816????Accepted Submission(s): 908

#include <iostream>#include <stdio.h>#include <memory.h>#include <string>#include <algorithm>#include <queue>#include <map>using namespace std;const int N = 155;const int INF = 99999999;map<string, int> mp;map<string, bool> bp;int way[N][N], dist[N];bool visit[N];string begin, end;int n, ans;void init() //初始化函数{ int i, j; mp.clear(); //清空映射mp bp.clear(); //清空映射bp for(i = 0; i < N; i++) for(j = 0; j < N; j++) if(i == j) way[i][j] = 0; else way[i][j] = INF;}void input() //输入函数{ int i, cost; ans = 1; string str1, str2; cin >> begin >> end; mp[begin] = 1; //mp映射该string为1 bp[begin] = true; //bp映射该string为true if(!bp[end]) { mp[end] = ++ans; bp[end] = true; } for(i = 1; i <= n; i++) { cin >> str1 >> str2 >> cost; if(!bp[str1]) { mp[str1] = ++ans; bp[str1] = true; } if(!bp[str2]) { mp[str2] = ++ans; bp[str2] = true; } way[mp[str1]][mp[str2]] = way[mp[str2]][mp[str1]] = cost; }}void spfa(){ int i, now; memset(visit, false, sizeof(visit)); for(i = 0; i <= ans; i++) dist[i] = INF; dist[1] = 0; queue<int> Q; Q.push(1); visit[1] = true; while(!Q.empty()) { now = Q.front(); Q.pop(); visit[now] = false; for(i = 1; i <= ans; i++) { if(dist[i] > dist[now] + way[now][i]) { dist[i] = dist[now] + way[now][i]; if(visit[i] == false) { Q.push(i); visit[i] = true; } } } }}int main(){ while(scanf("%d", &n)) { if(n == -1) break; init(); input(); spfa(); if(dist[mp[end]] != INF) printf("%d\n", dist[mp[end]]); else printf("-1\n"); } return 0;}

?

?