注意:
1、去重边
2、终点和起点一样,应当输出0
3、是无向图
AC代码
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 150 + 5; int vis[maxn], d[maxn], w[maxn][maxn]; map<string, int>Hash; int cur; int get_ID(string &p) { if(!Hash.count(p)) Hash[p] = cur++; return Hash[p]; } struct point{ int d, u; point(){ } point(int d, int u):d(d), u(u) { } bool operator < (const point& p) const { return d > p.d; } }; string s, e; int dijkstra(int n) { int x = get_ID(s), y = get_ID(e); for(int i = 0; i < n; ++i) d[i] = inf; d[x] = 0; memset(vis, 0, sizeof(vis)); priority_queue<point>Q; Q.push(point(0, x)); //将起点加入队列 while(!Q.empty()) { point p = Q.top(); Q.pop(); int u = p.u; if(u == y) return d[y]; if(vis[u]) continue; vis[u] = 1; for(int i = 0; i < n; ++i) { if(d[i] > d[u] + w[u][i]) { //update d[i] = d[u] + w[u][i]; if(d[i] > inf) d[i] = inf; Q.push(point(d[i], i)); } } } return -1; } int main() { int n; while(scanf("%d", &n) == 1 && n != -1) { memset(w, inf, sizeof(w)); Hash.clear(); cur = 0; cin >> s >> e; string x, y; int cost; for(int i = 0; i < n; ++i) { cin >> x >> y >> cost; int u = get_ID(x), v = get_ID(y); w[v][u] = w[u][v] = min(w[u][v], cost); //去重边 } printf("%d\n", dijkstra(Hash.size())); } return 0; }
如有不当之处欢迎指出!