专业做冻货的网站,网页设计导航栏内容,中小型网站建设精英,河南郑州百姓网P2149 Elaxia的路线 D e s c r i p t i o n \mathrm{Description} Description
给定 n n n 个点#xff0c; m m m 条边的无向图#xff0c;求 2 2 2 个点对间最短路的最长公共路径 S o l u t i o n \mathrm{Solution} Solution
最短路有可能不唯一#xff0c;所以公共路…P2149 Elaxia的路线 D e s c r i p t i o n \mathrm{Description} Description
给定 n n n 个点 m m m 条边的无向图求 2 2 2 个点对间最短路的最长公共路径 S o l u t i o n \mathrm{Solution} Solution
最短路有可能不唯一所以公共路径的长度就有可能不同。
将 2 2 2 条最短路都会经过的边包括同向和异向记录出来并建立 1 1 1 个新图那么由于最短路可以看做一条链一定不会走环故新图必定是一个 有向无环图 简称 D A G \mathrm{DAG} DAG而 D A G \mathrm{DAG} DAG 图上就可以跑 DP 来求解最长链由于找出的是 2 2 2 条最短路都经过的边所以最长链其实就是 2 2 2 条最短路的最长公共路径。
故该问题得以解决。 C o d e Code Code
#include bits/stdc.h
#define int long longusing namespace std;typedef pairint, int PII;
typedef long long LL;const int SIZE 1e6 10;int N, M;
int X1, Y1, X2, Y2;
int h[SIZE], hs[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;
int D[4][SIZE], Vis[SIZE], in[SIZE], q[SIZE], hh, tt -1;
int F[SIZE];void add(int h[], int a, int b, int c)
{e[idx] b, ne[idx] h[a], w[idx] c, h[a] idx ;
}void Dijkstra(int Start, int dist[])
{for (int i 1; i N; i )dist[i] 1e18, Vis[i] 0;priority_queuePII, vectorPII, greaterPII Heap;Heap.push({0, Start}), dist[Start] 0;while (Heap.size()){auto Tmp Heap.top();Heap.pop();int u Tmp.second;if (Vis[u]) continue;Vis[u] 1;for (int i h[u]; ~i; i ne[i]){int j e[i];if (dist[j] dist[u] w[i]){dist[j] dist[u] w[i];Heap.push({dist[j], j});}}}
}void Topsort()
{hh 0, tt -1;for (int i 1; i N; i )if (!in[i])q[ tt] i;while (hh tt){int u q[hh ];for (int i hs[u]; ~i; i ne[i]){int j e[i];if ((-- in[j]) 0)q[ tt] j;}}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(h, -1, sizeof h);memset(hs, -1, sizeof hs);cin N M X1 Y1 X2 Y2;int u, v, c;while (M --){cin u v c;add(h, u, v, c), add(h, v, u, c);}Dijkstra(X1, D[0]), Dijkstra(Y1, D[1]);Dijkstra(X2, D[2]), Dijkstra(Y2, D[3]);for (int i 1; i N; i )for (int j h[i]; ~j; j ne[j]){int k e[j];if (D[0][i] w[j] D[1][k] D[0][Y1] D[2][i] w[j] D[3][k] D[2][Y2])add(hs, i, k, w[j]), in[k] ;}Topsort();for (int it 0; it tt; it ){int i q[it];for (int j hs[i]; ~j; j ne[j]){int k e[j];F[k] max(F[k], F[i] w[j]);}}int Result 0;for (int i 1; i N; i )Result max(Result, F[i]);memset(hs, -1, sizeof hs);memset(F, 0, sizeof F);memset(in, 0, sizeof in);for (int i 1; i N; i )for (int j h[i]; ~j; j ne[j]){int k e[j];if (D[0][i] w[j] D[1][k] D[0][Y1] D[3][i] w[j] D[2][k] D[2][Y2])add(hs, i, k, w[j]), in[k] ;//, cout i k endl;}Topsort();for (int it 0; it tt; it ){int i q[it];for (int j hs[i]; ~j; j ne[j]){int k e[j];F[k] max(F[k], F[i] w[j]);}}for (int i 1; i N; i )Result max(Result, F[i]);cout Result endl;return 0;
}
