|
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 0x3f3f3f3f struct edgeType{ int to; int cost; edgeType(int ito,int icost){ to = ito; cost = icost; } }; struct vertexType{ vector<edgeType> edge; int dis; vertexType(){ edge.clear(); dis = MAXN; } }; vector<vertexType> vertex; struct cmp{ bool operator () (int a,int b){ return vertex[a].dis > vertex[b].dis; } }; int main(){ int n = 0,m = 0; int casecnt = 0; while (cin >> n >> m) { if (m == 0 && n == 0) { break; } casecnt++; vertex.clear(); for (int i = 0; i <= n; i++) { vertex.push_back(vertexType()); } for (int i = 0; i < m; i++) { int a = 0,b = 0,c = 0; cin >> a >> b >> c; vertex[a].edge.push_back(edgeType(b,c)); vertex[b].edge.push_back(edgeType(a,c)); } bool vis[502]; memset(vis, 0, sizeof(vis)); vertex[1].dis = 0; priority_queue<int,vector<int>,cmp> q; q.push(1); while (!q.empty()) { int cur = q.top(); q.pop(); vis[cur] = true; for (int i = 0; i < vertex[cur].edge.size(); i++) { edgeType nextedge = vertex[cur].edge[i]; if (vis[nextedge.to]) { continue; } if (vertex[nextedge.to].dis > vertex[cur].dis + nextedge.cost) { vertex[nextedge.to].dis = vertex[cur].dis + nextedge.cost; q.push(nextedge.to); } } } double res = 0; int pt1 = 1,pt2 = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < vertex[i].edge.size(); j++) { double terpos = ((double)vertex[i].dis + (double)vertex[vertex[i].edge[j].to].dis + (double)vertex[i].edge[j].cost)/2; double judge = max(terpos,max((double)vertex[i].dis,(double)vertex[vertex[i].edge[j].to].dis)); if (judge > res) { if (judge != vertex[i].dis && judge != vertex[vertex[i].edge[j].to].dis) { res = judge; pt1 = min(i,vertex[i].edge[j].to); pt2 = max(i,vertex[i].edge[j].to); }else if(judge == (double)vertex[i].dis){ res = vertex[i].dis; pt1 = i,pt2 = i; }else{ res = vertex[vertex[i].edge[j].to].dis; pt1 = vertex[i].edge[j].to,pt2 = vertex[i].edge[j].to; } } } } cout << "System #" << casecnt << endl; cout.setf(ios::fixed); cout << "The last domino falls after " << setprecision(1) << res << " seconds, "; cout.unsetf(ios::fixed); if (pt1 != pt2) { cout << "between key dominoes " << pt1 << " and " << pt2 << '.' << endl; }else{ cout << "at key domino " << pt1 << '.' << endl; } cout << endl; } return 0; } |
题我就没读懂。。。
其实是这样，把每一个key domino当做节点，他们之间的骨牌数目当作边权，用dijkstra处理一下得到的就是骨牌倒道该节点的最短时间，接下来我们要考虑在中间倒完的情况。
如果在两个节点中间倒完的话，也就意味着从起点经过两个key domino到终点，左右两边走过的时间是一样的，所以我们可以用(dis[a]+dis[b]+edge.cost)/2这个就可以求出在两点之间倒完需要多少时间，我们把每条边都这样过一遍，如果求出来的这个值比左右两边节点的dis都大，说明倒在中间，如果正好等于某一个节点的dis值，就把那个节点当作终点，把所有的边都这样过完之后，找到最大的(dis[a]+dis[b]+edge.cost)/2对应的终止情形，就是答案。
