题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=7175
题解：先用dijkstra在原图上跑出最短路，然后将所有的最短路重新建图建出最短路图，建完后的图中可能包含0 0环，对结果不造成影响所以通过tarjan缩点，缩出DAG，最后在DAG上dp(其实是记搜)，求得DAG上的最长路。
代码：
1 #include2 #include point& x)const 36 { 37 return x.dis < dis; 38 } 39 }; 40 priority_queue3 #include 4 #include 5 #include pq; 41 42 struct node { 43 int to, val, w; 44 }; 45 struct spnode { 46 int v, w; 47 }; 48 vector G[N]; 49 vector SPG[N]; 50 vector DAG[N]; 51 52 void dijkstra(int t) { 53 54 memset(dis, 0x3f, sizeof(dis)); 55 dis[t] = 0; 56 pq.push({ 0,t }); 57 while (!pq.empty()) { 58 point tmp = pq.top(); 59 pq.pop(); 60 int p = tmp.pos, d = tmp.dis; 61 if (vis[p]) continue; 62 vis[p] = 1; 63 for (int i = 0; i < G[p].size(); i++) { 64 int frt = G[p][i].to, dist = G[p][i].val; 65 if (!vis[frt] && dis[p] + dist < dis[frt]) { 66 dis[frt] = dis[p] + dist; 67 pq.push({ dis[frt],frt }); 68 } 69 } 70 } 71 return; 72 } 73 74 void getspg() { 75 for (int i = 1; i ) { 76 if (dis[i] == inf) continue; 77 for (int j = 0; j < G[i].size(); j++) { 78 int v = G[i][j].to; 79 int w = G[i][j].val; 80 if (dis[i] + w == dis[v]) { 81 SPG[i].push_back({ v,G[i][j].val,G[i][j].w }); 82 } 83 } 84 } 85 } 86 87 void tarjan(int u) { 88 dfn[u] = ++dfncnt; 89 low[u] = dfncnt; 90 st.push(u); 91 ins[u] = true; 92 for (int i = 0; i < SPG[u].size(); i++) { 93 int v = SPG[u][i].to; 94 if (!dfn[v]) { 95 tarjan(v); 96 low[u] = min(low[u], low[v]); 97 } 98 else if (ins[v]) { 99 low[u] = min(low[u], dfn[v]); 100 } 101 } 102 if (dfn[u] == low[u]) { 103 int v; 104 ++scccnt; 105 do { 106 v = st.top(); 107 st.pop(); 108 ins[v] = false; 109 scc[v] = scccnt; 110 } while (u != v); 111 } 112 } 113 114 void getdag() { 115 for (int i = 1; i ) { 116 if (!dfn[i]) { 117 tarjan(i); 118 } 119 } 120 for (int u = 1; u ) { 121 for (int j = 0; j < SPG[u].size(); j++) { 122 int v = SPG[u][j].to; 123 int w = SPG[u][j].w; 124 if (scc[u] != scc[v]) { 125 DAG[scc[u]].push_back({ scc[v],w }); 126 } 127 } 128 } 129 } 130 131 int search(int u) { 132 if (vis[u]) return dp[u]; 133 vis[u] = true; 134 for (int i = 0; i < DAG[u].size(); i++) { 135 int v = DAG[u][i].v; 136 int w = DAG[u][i].w; 137 dp[u] = max(dp[u], search(v) + w); 138 } 139 return dp[u]; 140 } 141 142 void init() { 143 for (int i = 0; i 10; i++) G[i].clear(); 144 for (int i = 0; i 10; i++) SPG[i].clear(); 145 for (int i = 0; i 10; i++) DAG[i].clear(); 146 memset(dp, -0x3f, sizeof(dp)); 147 memset(vis, 0, sizeof(vis)); 148 memset(scc, 0, sizeof(scc)); 149 memset(ins, false, sizeof(ins)); 150 memset(dfn, 0, sizeof(dfn)); 151 memset(low, 0, sizeof(low)); 152 while (!st.empty()) st.pop(); 153 dfncnt = 0, scccnt = 0; 154 } 155 156 signed main() { 157 158 ios::sync_with_stdio(false); 159 cin.tie(0), cout.tie(0); 160 int T; 161 cin >> T; 162 while (T--) { 163 init(); 164 //int n, m; 165 cin >> n >> m; 166 for (; m; --m) { 167 int u, v, w1, w2; 168 cin >> u >> v >> w1 >> w2; 169 G[u].push_back({ v,w1,w2 }); 170 } 171 dijkstra(1); 172 getspg(); 173 getdag(); 174 memset(vis, 0, sizeof(vis)); 175 dp[scc[n]] = 0; 176 search(scc[1]); 177 cout << dis[n] << " " << dp[scc[1]] << "\n"; 178 } 179 180 return 0; 181 }
永远热爱，永远向着光。
Original: https://www.cnblogs.com/wabi/p/16536648.html
Author: Kyrizer_W
Title: 2022杭电多校第四场B-Link with Running
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587876/
转载文章受原作者版权保护。转载请注明原作者出处！