题意:给了一个有向图，和一个地点A，每个点都有头牛都想去A点，玩好后在从A点回到家（之前的点)。
问：每头牛都走最近的路，哪头牛走的最远，路程是多少。
思路：裸体，想清楚就行，开始一个反向建图求A到每个点的最短路，再正常建图求A到每个点的最短路，然后对应的相加，找个最大值
迪杰斯特拉+邻接表+优先队列优化
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; int tot,n,m,headx; int ver[110000],edge[110000],next[110000],head[110000],d[1100],vis[1100],rem[1100],xx[110000],yy[110000],zz[110000]; priority_queue<pair<int,int> >que; void add(int x,int y,int z) { ver[++tot] = y, edge[tot] = z, next[tot] = head[x], head[x] = tot; } void dijistra() { memset(d,110,sizeof(d)); d[headx] = 0; que.push(make_pair(0,headx)); while(que.size()) { int x = que.top().second; que.pop(); if(vis[x] == 1) continue; vis[x] = 1; for(int i=head[x] ; i ; i=next[i]) { int y=ver[i]; int z=edge[i]; if(d[y] > d[x] + z) { d[y] = d[x] + z; que.push(make_pair(-d[y],y)); } } } } void clearr() { memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); memset(edge,0,sizeof(edge)); memset(ver,0,sizeof(ver)); memset(next,0,sizeof(next)); } int main() { ios::sync_with_stdio(false); cin>>n>>m>>headx; FOR(i,1,m) { int x, y, z; cin>>xx[i]>>yy[i]>>zz[i]; } FOR(i,1,m) add(xx[i],yy[i],zz[i]); dijistra(); for(int i=1;i<=n;++i) rem[i]+=d[i]; clearr(); FOR(i,1,m) add(yy[i],xx[i],zz[i]); dijistra(); for(int i=1;i<=n;++i) rem[i]+=d[i]; int maxx=-1; FOR(i,1,n) maxx = max(maxx , rem[i]); cout<<maxx<<endl; }