题目 2406:
信息学奥赛一本通T1497-农场派对
时间限制: 2s 内存限制: 192MB 提交: 40 解决: 13
题目描述
原题来自：USACO 2007 Feb. Silver
N(1≤N≤1000) 头牛要去参加一场在编号为 x(1≤x≤N) 的牛的农场举行的派对。有 M(1≤M≤100000) 条有向道路，每条路长 Ti(1≤Ti≤100)；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这 N 头牛的最短路径（一个来回）中最长的一条的长度。 特别提醒：可能有权值不同的重边。输入格式
第 1 行：3 个空格分开的整数 N,M,X；
第 2…M 行：3 个空格分开的整数 Ai,Bi,Ti ，表示有一条从 Ai 到 Bi 的路，长度为 Ti 。输出格式
一行一个数，表示最长最短路的长度。
样例输入
复制
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3样例输出
复制
10
思路：
只需要考虑建立反向边图，将各点到x的最短路，转换为x点到各点的反向变图最短路。
#include<bits/stdc++.h> using namespace std; typedef pair<int, int>PII; const int N = 1010, M = 100010; int h1[N], h2[N], e1[M], e2[M], ne1[M], ne2[M], w1[M], w2[M], idx1, idx2; bool st1[N], st2[N]; int dis1[N], dis2[N]; int n, m, x; void add1(int a, int b, int c) {e1[idx1] = b, w1[idx1] = c, ne1[idx1] = h1[a], h1[a] = idx1++; } void add2(int a, int b, int c) {e2[idx2] = b, w2[idx2] = c, ne2[idx2] = h2[a], h2[a] = idx2++; } void dij(int x, int h[], bool st[], int dis[], int w[], int ne[], int idx,int e[]) {priority_queue<PII, vector<PII>, greater<PII>>q;q.push({ 0,x });dis[x] = 0;while (q.size()) {auto t = q.top();q.pop();int v = t.second;if (st[v]) {continue;}st[v] = true;for (int i = h[v]; ~i; i = ne[i]) {int j = e[i];if (st[j]) {continue;}if (dis[j] > dis[v] + w[i]) {dis[j] = dis[v] + w[i];q.push({ dis[j],j });}}} } void solve() {cin >> n >> m >> x;memset(h1, -1, sizeof h1);memset(h2, -1, sizeof h2);memset(dis1, 0x3f, sizeof dis1);memset(dis2, 0x3f, sizeof dis2);for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;add1(a, b, c);add2(b, a, c);}dij(x, h1, st1, dis1, w1, ne1, idx1,e1);dij(x, h2, st2, dis2, w2, ne2, idx2,e2);int ans = 0;for (int i = 1; i <= n; i++) {ans = max(ans, dis1[i] + dis2[i]);}cout << ans; }int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;//cin >> T;solve();return 0; }