POJ 3114 Countries in War(强连通+最短路)
in poj 短路 war 连通
2023-09-14 09:07:57 时间
POJ 3114 Countries in War
题意:给定一个有向图。强连通分支内传送不须要花费,其它有一定花费。每次询问两点的最小花费
思路:强连通缩点后求最短路就可以
代码:
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; const int MAXNODE = 505; const int MAXEDGE = 255005; typedef int Type; const Type INF = 0x3f3f3f3f; struct Edge { int u, v; Type dist; Edge() {} Edge(int u, int v, Type dist) { this->u = u; this->v = v; this->dist = dist; } }; struct HeapNode { Type d; int u; HeapNode() {} HeapNode(Type d, int u) { this->d = d; this->u = u; } bool operator < (const HeapNode& c) const { return d > c.d; } }; struct Dijkstra { int n, m; Edge edges[MAXEDGE]; int first[MAXNODE]; int next[MAXEDGE]; bool done[MAXNODE]; Type d[MAXNODE]; void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; } void add_Edge(int u, int v, Type dist) { edges[m] = Edge(u, v, dist); next[m] = first[u]; first[u] = m++; } int dijkstra(int s, int t) { priority_queue<HeapNode> Q; for (int i = 0; i < n; i++) d[i] = INF; d[s] = 0; memset(done, false, sizeof(done)); Q.push(HeapNode(0, s)); while (!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if (u == t) return d[t]; if (done[u]) continue; done[u] = true; for (int i = first[u]; i != -1; i = next[i]) { Edge& e = edges[i]; if (d[e.v] > d[u] + e.dist) { d[e.v] = d[u] + e.dist; Q.push(HeapNode(d[e.v], e.v)); } } } return -1; } } gao; const int N = 505; int n, m; vector<Edge> g[N]; int pre[N], dfn[N], dfs_clock, sccn, sccno[N]; stack<int> S; void dfs_scc(int u) { pre[u] = dfn[u] = ++dfs_clock; S.push(u); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].v; if (!pre[v]) { dfs_scc(v); dfn[u] = min(dfn[u], dfn[v]); } else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]); } if (pre[u] == dfn[u]) { sccn++; while (1) { int x = S.top(); S.pop(); sccno[x] = sccn; if (x == u) break; } } } void find_scc() { dfs_clock = sccn = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for (int i = 1; i <= n; i++) if (!pre[i]) dfs_scc(i); } int main() { while (~scanf("%d%d", &n, &m) && n) { for (int i = 1; i <= n; i++) g[i].clear(); int u, v, w; while (m--) { scanf("%d%d%d", &u, &v, &w); g[u].push_back(Edge(u, v, w)); } find_scc(); gao.init(n); for (int u = 1; u <= n; u++) { for (int j = 0; j < g[u].size(); j++) { int v = g[u][j].v; if (sccno[u] == sccno[v]) continue; gao.add_Edge(sccno[u] - 1, sccno[v] - 1, g[u][j].dist); } } int q; scanf("%d", &q); while (q--) { scanf("%d%d", &u, &v); int tmp = gao.dijkstra(sccno[u] - 1, sccno[v] - 1); if (tmp == -1) printf("Nao e possivel entregar a carta\n"); else printf("%d\n", tmp); } printf("\n"); } return 0; }
相关文章
- 【错误记录】PyCharm 运行 Python 程序报错 ( SyntaxError: Non-ASCII character ‘xe5‘ in file x.py on line 1, but )
- ORA-01719: outer join operator (+) not allowed in operand of OR or IN ORACLE 报错 故障修复 远程处理
- ORA-23460: missing value for column string in resolution method “string” for “string”.”string”.”string” ORACLE 报错 故障修复 远程处理
- ORA-29531: no method string in class string ORACLE 报错 故障修复 远程处理
- ORA-38704: Checksum error in flashback database log file header. ORACLE 报错 故障修复 远程处理
- ORA-41673: sequence attribute not allowed in rule conditions using table aliases ORACLE 报错 故障修复 远程处理
- ORA-02482: Syntax error in event specification (string) ORACLE 报错 故障修复 远程处理
- ORA-08276: No room in nameserver for pid ORACLE 报错 故障修复 远程处理
- ORA-13283: failure to get new geometry object for conversion in place ORACLE 报错 故障修复 远程处理
- Oracle数据库中ORDER BY排序和查询按IN条件的顺序输出
- 高可用Hadoop平台-Hue In Hadoop详解大数据
- net.sf.json.JSONException: There is a cycle in the hierarchy! 异常解决详解编程语言
- 关键字使用Oracle中的Replace函数替代IN关键字(oracle替代in)
- MySQL查询优化:从IN中获取更高性能(mysql查询优化in)
- MySQL中使用IN排序查询记录(mysql按in排序)
- 使用Oracle IN操作符提高工作效率(oraclein操作符)
- 深入Linux内核:IN后缀操作系统之旅(linux系统in后缀)
- MYSQL中IN关键字如何高效处理大量数据(mysql中in关键字)
- Oracle的IN走索引技术(in走索引 oracle)
- MySQL不支持IN运算符如何解决(mysql 不支持in)
- 探索Oracle中IN查询的精彩之处(oracle中的in查询)
- Oracle中两个IN叠加的查询技巧(oracle两个in叠加)
- 探索Oracle在今天的科技时代的实用之道(oracle in ?句)