Elaxia的路线 SDOI2009 最短路

2019-11-14 09:17:44

字体：大中小

来源：转载

供稿：网友

题目描述

最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们希望在节约时间的前提下，一起走的时间尽可能的长。现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路口，M条路，经过每条路都需要一定的时间。具体地说，就是要求无向图中，两对点间最短路的最长公共路径。

输入输出格式

输入格式：

第一行：两个整数N和M（含义如题目描述）。第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别 x1,y1和x2,y2）。接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之间有一条路，经过这条路所需要的时间为l。

输出格式：

一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）

说明

对于30%的数据，N ≤ 100；对于60%的数据，N ≤ 1000；对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。

Analysis

题意已经很粗暴了首先要找到哪些边在最短路上，可以想到如果dis_to_st[i] + dis_to_ed[j] + w[i, j] = 最短路的话，这条边处在最短路上为了求出这些距离我们把给出的四个点我们分别跑spfa一共是四次，再把共有的边连成一张新的图拓扑排序做递推，len[u]=max(len[v]+w,len[u]) $len[u]=/max(len[v] + w, len[u])$ 就这样，写写停停中途打了两个小时fgo一个下午吧

Code

#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorithm>#include <string>#include <vector>#include <deque>#include <list>#include <set>#include <map>#include <stack>#include <queue>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#define debug puts("-----")#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)#define fill(x, t) memset(x, t, sizeof(x))#define min(x, y) x<y?x:y#define max(x, y) x>y?x:y#define PI (acos(-1.0))#define EPS (1e-8)#define INF (1<<30)#define ll long long#define db double#define ld long double#define N 1501#define E N * N / 2 + 1#define MOD 100000007#define L 255using namespace std;struct edge{int x, y, w, next;}e[E], g[E];int inQueue[N], mark[E], dis1[N], dis2[N], ind[N], lsE[N], lsG[N], dp[N];inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v;}inline int addEdgeE(int &cnt, const int &x, const int &y, const int &w){ e[++ cnt] = (edge){x, y, w, lsE[x]}; lsE[x] = cnt; return 0;}inline int addEdgeG(int &cnt, const int &x, const int &y, const int &w){ g[++ cnt] = (edge){x, y, w, lsG[x]}; lsG[x] = cnt; ind[y] += 1; return 0;}inline int spfa1(const int &st, const int &ed){ fill(inQueue, 0); inQueue[st] = 1; fill(dis1, 63); dis1[st] = 0; queue<int>q; q.push(st); while (!q.empty()){ int now = q.front(); q.pop(); for (int i = lsE[now]; i; i = e[i].next){ if (dis1[now] + e[i].w < dis1[e[i].y]){ dis1[e[i].y] = dis1[now] + e[i].w; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; q.push(e[i].y); } } } inQueue[now] = 0; } return dis1[ed];}inline int spfa2(const int &st, const int &ed){ fill(inQueue, 0); inQueue[st] = 1; fill(dis2, 63); dis2[st] = 0; queue<int>q; q.push(st); while (!q.empty()){ int now = q.front(); q.pop(); for (int i = lsE[now]; i; i = e[i].next){ if (dis2[now] + e[i].w < dis2[e[i].y]){ dis2[e[i].y] = dis2[now] + e[i].w; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; q.push(e[i].y); } } } inQueue[now] = 0; } return dis2[ed];}int main(void){ int n = read(), m = read(); int st1 = read(), ed1 = read(), st2 = read(), ed2 = read(); int edgeCntE = 0, edgeCntG = 0; rep(i, 1, m){ int x = read(), y = read(), w = read(); addEdgeE(edgeCntE, x, y, w); addEdgeE(edgeCntE, y, x, w); } int stpath1 = spfa1(st1, ed1) & spfa2(ed1, st1); // PRintf("%d/n", stpath1); rep(i, 1, edgeCntE){ if (dis1[e[i].x] + dis2[e[i].y] + e[i].w == stpath1 || dis2[e[i].x] + dis1[e[i].y] + e[i].w == stpath1){ mark[i] += 1; } } int stpath2 = spfa1(st2, ed2) & spfa2(ed2, st2); // printf("%d/n", stpath2); rep(i, 1, edgeCntE){ if (dis1[e[i].x] + dis2[e[i].y] + e[i].w == stpath2 || dis2[e[i].x] + dis1[e[i].y] + e[i].w == stpath2){ mark[i] += 1; } } rep(i, 1, edgeCntE){ if (mark[i] == 2 && dis1[e[i].x] < dis1[e[i].y]){ addEdgeG(edgeCntG, e[i].x, e[i].y, e[i].w); // printf("x = %d y = %d w = %d/n", e[i].x, e[i].y, e[i].w); } } queue<int>q; rep(i, 1, n){ if (!ind[i]){ q.push(i); } } int ans = 0; while (!q.empty()){ int now = q.front(); q.pop(); // printf("%d ", now); ans = max(ans, dp[now]); for (int i = lsG[now]; i; i = g[i].next){ if (!-- ind[g[i].y]){ q.push(g[i].y); dp[g[i].y] = max(dp[now] + g[i].w, dp[g[i].y]); } } } // printf("/n%d , %d/n", stpath1, stpath2); printf("%d/n", ans); return 0;}

上一篇：poj 1328 区间，贪心

下一篇：动态规划与矩阵快速幂