【最短路】PAT L3-011. 直捣黄龙(求最短路条数，三个关键词优先，最短路路径)

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <stack> #include <map> using namespace std; const int INF = 0x3f3f3f3f; const int N = 210; const double esp = 1e-6; int n,m; struct point { int kill; string name; }a[N]; map<string,int> p; int mp[N][N]; int dist[N],num[N],kill[N],vis[N],jie[N],path[N]; void dijsk(int begin,int end) { memset(vis,0,sizeof(vis)); memset(kill,0,sizeof(kill)); memset(num,0,sizeof(num)); memset(jie,0,sizeof(jie)); for(int i = 0; i < n; i++) dist[i] = INF; dist[begin] = 0; num[begin] = 1; jie[begin] = 0; kill[begin] = a[begin].kill; int next; for(int i = 0; i < n; i++) { int MIN = INF; for(int j = 0; j < n; j++) { if(!vis[j]) { if(dist[j] < MIN) { MIN = dist[j]; next = j; } } } if(MIN == INF) break; vis[next] = 1; /* 一切均在更新过程中做文章 path[j] 代表目前j点的前一个最短连接结点 dist[j] 代表目前j点距起点的最小距离 num[j] 代表目前起点到j点的最短路条数 jie[j] 代表目前起点到j点在最短路下解放的最多城市数 kill[j] 代表目前起点到j点在最短路下解放最多城市数下最多杀敌数 */ for(int j = 0; j < n; j++) { if(!vis[j]) { if(dist[j] > mp[next][j]+dist[next]) { dist[j] = mp[next][j]+dist[next]; num[j] = num[next]; kill[j] = kill[next]+a[j].kill; jie[j] = jie[next]+1; path[j] = next; } else if(dist[j] == mp[next][j]+dist[next]) { num[j] += num[next]; if(jie[j] < jie[next]+1) { jie[j] = jie[next]+1; kill[j] = kill[next]+a[j].kill; path[j] = next; } else if(jie[j] == jie[next]+1) { if(kill[j] < kill[next]+a[j].kill) { kill[j] = kill[next]+a[j].kill; path[j] = next; } } } } } } stack<int> q; int temp = end; while(temp != begin) { q.push(temp); temp = path[temp]; } cout << a[0].name; while(!q.empty()) { int x = q.top(); q.pop(); cout << "->" << a[x].name; } cout << endl; printf("%d %d %d\n",num[end],dist[end],kill[end]); } void init() { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j) mp[i][j] = INF; else mp[i][j] = 0; } int main() { cin >> n >> m; string x,y; cin >> x >> y; a[0].name = x; a[0].kill = 0; p[x] = 0; int begin_num,end_num; for(int i = 1; i < n; i++) { getchar(); string s; int kills; cin >> s >> kills; p[s] = i; a[i].name = s; a[i].kill = kills; if(s == y) end_num = i; } init(); while(m--) { int c; cin >> x >> y >> c; int a = p[x]; int b = p[y]; if(mp[a][b] > c) mp[a][b] = mp[b][a] = c; } dijsk(0,end_num); return 0; }