题目连接
题意： 给定一个无向图，每一个边有两个属性。长度和一个字母‘L'，’O'，‘V’。‘E'中的一个。从1点開始到达n点，每次必须依照L -> O -> V -> E -> ... -> E的顺序。到达终点时候必须经过E边分析： 对于这样的对边的限制，比較简单的方法是将一个点拆成若干个点。由于经过’L'到达点p的状态和经过‘O'到达点p的状态时不一样的，第一个之后仅仅能经过’O'边。而第二个仅仅能经过‘V'边，所以经过不同的边到达同一个点的时候相应的状态应该分开。也就是将点拆分成四个点。分别表示经过四种边到达p点。注意： 图能够有自环。也能够仅仅有一个点 路径必须至少有一个LOVE 路径长度尽可能小，长度若相等，那么LOVE的数量尽可能多 Dijkstra方法：（一个点的时候直接特判。避免不必要的麻烦） const LL INF = 1e18; const int MAXV = 10000; struct Edge { LL from, to, dist; }; struct HeapNode { LL d, u, num; bool operator < (const HeapNode& rhs) const { return d > rhs.d; } }; struct Dijkstra { int n; //n:点数 m:暂时变量 vector<Edge> edges; //存储全部的边 vector<int> G[MAXV];//每一个点的全部相邻边序号 bool done[MAXV]; // 是否已永久标号 LL d[MAXV]; // s起点到各个点的距离 LL num[MAXV]; void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int dist) { G[from].push_back(edges.size()); edges.push_back((Edge) { from, to, dist }); } void dijkstra(int s) { priority_queue<HeapNode> Q; for(int i = 0; i < n; i++) d[i] = INF; CLR(num, 0); d[s] = 0; memset(done, 0, sizeof(done)); Q.push((HeapNode) { 0, s, 0 }); while(!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if(done[u]) continue; done[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (d[e.to] == d[u] + e.dist) num[e.to] = max(num[e.to], num[x.u] + 1); if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; num[e.to] = num[x.u] + 1; Q.push((HeapNode) { d[e.to], e.to, num[e.to] }); } } } } } dij; LL chk[4]; int main() { int T; RI(T); FE(kase, 1, T) { REP(i, 4) chk[i] = INF; int n, m, u, v, d, op; char type; RII(n, m); dij.init(n << 2); REP(i, m) { scanf("%d%d%d %c", &u, &v, &d, &type); u--; v--; if (type == 'L') op = 0; else if (type == 'O') op = 1; else if (type == 'V') op = 2; else op = 3; chk[op] = min(chk[op], (LL)d); dij.AddEdge(u + (op + 3) % 4 * n, v + op * n, d); dij.AddEdge(v + (op + 3) % 4 * n, u + op * n, d); } printf("Case %d: ", kase); if (n == 1) { REP(i, 4) if (chk[i] == INF) { puts("Binbin you disappoint Sangsang again, damn it!"); goto end; } printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n" , chk[0] + chk[1] + chk[2] + chk[3], 1); end:; } else { dij.dijkstra(3 * n); if (dij.d[4 * n - 1] == INF) puts("Binbin you disappoint Sangsang again, damn it!"); else { printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %I64d LOVE strings at last.\n" , dij.d[4 * n - 1], dij.num[4 * n - 1] / 4); } } } return 0; } spfa方法：（一个点也是特判，加点方式与Dijkstra同样） const LL INF = 1e18; const int MAXV = 10000; struct Edge { int from, to, dist; }; struct SPFA { int n; LL d[MAXV]; int num[MAXV]; vector<Edge> edges; vector<int> G[MAXV]; bool inq[MAXV]; void init(int n) { this->n = n; edges.clear(); REP(i, n) G[i].clear(); } void AddEdge(int from, int to, int dist) { G[from].push_back(edges.size()); edges.push_back((Edge) {from, to, dist}); } void spfa(int s) { queue<int> q; CLR(inq, false); CLR(num, 0); REP(i, n) d[i] = INF; d[s] = 0; q.push(s); inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; REP(i, G[u].size()) { Edge& e = edges[G[u][i]]; if (d[e.to] == d[u] + e.dist && num[u] + 1 > num[e.to]) { num[e.to] = num[u] + 1; if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; } } if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; num[e.to] = num[u] + 1; if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; } } } } } } spfa; LL chk[4]; int main() { int T; RI(T); FE(kase, 1, T) { REP(i, 4) chk[i] = INF; int n, m, u, v, d, op; char type; RII(n, m); spfa.init(n << 2); REP(i, m) { scanf("%d%d%d %c", &u, &v, &d, &type); u--; v--; if (type == 'L') op = 0; else if (type == 'O') op = 1; else if (type == 'V') op = 2; else op = 3; chk[op] = min(chk[op], (LL)d); spfa.AddEdge(u + (op + 3) % 4 * n, v + op * n, d); spfa.AddEdge(v + (op + 3) % 4 * n, u + op * n, d); } printf("Case %d: ", kase); if (n == 1) { REP(i, 4) if (chk[i] == INF) { puts("Binbin you disappoint Sangsang again, damn it!"); goto end; } printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n" , chk[0] + chk[1] + chk[2] + chk[3], 1); end:; } else { spfa.spfa(3 * n); if (spfa.d[4 * n - 1] == INF) puts("Binbin you disappoint Sangsang again, damn it!"); else { printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n" , spfa.d[4 * n - 1], spfa.num[4 * n - 1] / 4); } } } return 0; }顺便弄一些自己的測试数据。方便查错。
4 4 1 2 1 L 2 1 1 O 1 3 1 V 3 4 1 E ans:4, 1 4 4 1 2 1 L 2 3 1 O 3 4 1 V 4 1 1 E ans:no 12 12 1 5 10 L 5 6 10 O 6 7 10 V 7 12 10 E 1 2 1 L 2 3 1 O 3 4 1 V 4 8 1 E 8 9 1 L 9 10 1 O 10 11 1 V 11 12 33 E ans:40, 2 12 12 1 5 10 L 5 6 10 O 6 7 10 V 7 12 10 E 1 2 1 L 2 3 1 O 3 4 1 V 4 8 1 E 8 9 1 L 9 10 1 O 10 11 1 V 11 12 34 E ans:40, 1 1 4 1 1 1 L 1 1 1 O 1 1 1 V 1 1 1 E ans:4, 1 2 8 1 1 2 L 1 1 1 O 1 1 1 V 1 1 1 E 1 2 3 L 2 1 1 O 1 2 1 V 2 1 1 E ans:5, 1 1 3 1 1 1 L 1 1 1 O 1 1 1 E ans:no 11 11 1 2 1 L 2 3 1 O 3 4 348 V 4 11 1000 E 1 5 50 L 5 6 50 O 6 7 50 V 7 8 50 E 8 9 50 L 9 10 50 O 10 4 50 V ans:1350 2
转载于:https://www.cnblogs.com/bhlsheji/p/5121013.html
相关资源：数据结构—成绩单生成器