Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.解题思路：题意抽象出来意思是给一个有向图，然后求所有点经过v点，再回到原点的所有最短路径中最长的一条。解题方法就是用两个dijkstra，分别求i到v的最短距离和v到i的最短距离，然后找出最大的即可。<code class="hljs handlebars has-numbering"><span class="xml"><span class="hljs-tag">求最短路径步骤算法步骤如下：<span class="hljs-attribute">G</span>=<span class="hljs-value">{V,E}</span><span class="hljs-attribute">1.</span> 初始时令 <span class="hljs-attribute">S</span>=<span class="hljs-value">{V0},T=V-S={其余顶点}，，T中顶点对应的距离值</span>若存在<<span class="hljs-attribute">V0</span>,<span class="hljs-attribute">Vi</span>></span>，d(V0,Vi)为<span class="hljs-tag"><<span class="hljs-title">V0,Vi</span>></span>弧上的权值若不存在<span class="hljs-tag"><<span class="hljs-title">V0,Vi</span>></span>，d(V0,Vi)为∞2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止</span></code>#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>using namespace std;const int maxn=1010;const int INF=0x7ffffff;int load[maxn][maxn];int v[maxn];int d1[maxn],d2[maxn];int n,m,x;int main(){while(scanf("%d %d %d",&n,&m,&x) != EOF){int a,b,c;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j) load[i][j]=INF;else if (i==j) load[i][i]=0;for(int i=0;i<m;i++){scanf("%d %d %d",&a,&b,&c);load[a][b]=min(load[a][b],c);}memset(v,0,sizeof(v));for(int i=1;i<=n;i++) d1[i]=INF;d1[x]=0;for(int i=0;i<n;i++){int x,ans=INF;for(int y=1;y<=n;y++) if(!v[y] && d1[y]<=ans) {ans=d1[y]; x=y;}v[x]=1;for(int y=1;y<=n;y++)if(d1[y]>d1[x]+load[x][y]) d1[y]=d1[x]+load[x][y];}memset(v,0,sizeof(v));for(int i=1;i<=n;i++) d2[i]=INF;d2[x]=0;for(int i=0;i<n;i++){int x,ans=INF;for(int y=1;y<=n;y++) if(!v[y] && d2[y]<=ans) {ans=d2[y];x=y;}v[x]=1;for(int y=1;y<=n;y++)if(d2[y]>d2[x]+load[y][x]) d2[y]=d2[x]+load[y][x];}int ans=0;for(int i=1;i<=n;i++){if(ans<d1[i]+d2[i]) ans=d1[i]+d2[i];}cout<<ans << endl;}return 0;}
头脑心灵再加上双脚的才是推销员。
