解题思路:求牛X到其余牛的最短路径的2倍就可以了,单元最短路
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> #include<vector> using namespace std; const int maxn = 1000+10; int n,m,x; struct Node{ int to;int cost; Node(){}; Node(int x,int y):to(x),cost(y){}; }node; vector<Node> E[maxn]; typedef pair<int,int> P; int d[maxn][maxn]; void dij(int s){ // priority_queue<P,vector<P>,greater<P> > pq; memset(d[s],0x3f,sizeof(d[s])); d[s][s]=0; pq.push(P(0,s)); while(!pq.empty()){ P p= pq.top(); pq.pop(); int v=p.second; // if(d[s][v] < p.first) continue; for(int i=0;i<E[v].size();i++){ int u=E[v][i].to; if(d[s][u] > d[s][v]+E[v][i].cost){ d[s][u] = d[s][v] + E[v][i].cost; pq.push(P(d[s][u],u)); } } } } int main(){ scanf("%d%d%d",&n,&m,&x); for(int i=0;i<m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); E[x].push_back(Node(y,z)); //E[y].push_back(Node(x,z)); } for(int i=1;i<=n;i++) dij(i); int ans=0; for(int i=1;i<=n;i++){ if(i==x){ continue; } ans=max(ans,d[i][x]+d[x][i]); } printf("%d\n",ans); return 0; }