首页 > 代码库 > UESTC 914 方老师的分身I Dijkstra

UESTC 914 方老师的分身I Dijkstra

2024-07-08 07:00:26   222人阅读

题意：求有向图的往返最短路的最长长度。

分析：求第一次到所有点的距离可以用一次Dijkstra求最短路求出来。考虑回来的路，想想就知道，从每个点回来的路即为将边的方向反转再求一次最短路后的结果。

所以此题为求两次最短路。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define Mod 1000000007using namespace std;#define N 1007int mp[N][N],n,m;int dis[N],vis[N],dis2[N];void Dijastra(int s,int *dis){    int now = s;    int i,k;    dis[now] = 0;    vis[now] = 1;    for(i=1;i<=n;i++)    {        for(k=1;k<=n;k++)  //order 1        {            if(mp[now][k] != Mod && dis[now] + mp[now][k] < dis[k])                dis[k] = dis[now] + mp[now][k];        }        int mini = Mod;   //order 2        for(k=1;k<=n;k++)        {            if(dis[k] < mini && !vis[k])            {                now = k;                mini = dis[k];            }        }        vis[now] = 1;    }}int main(){    int u,v,w,i,j,x;    while(scanf("%d%d%d",&n,&m,&x)!=EOF)    {        for(i=1;i<=n;i++)            dis[i] = Mod;        dis[x] = 0;        for(i=1;i<=n;i++)        {            for(j=i;j<=n;j++)                mp[i][j] = mp[j][i] = Mod;            mp[i][i] = 0;        }        while(m--)        {            scanf("%d%d%d",&u,&v,&w);            mp[u][v] = w;        }        memset(vis,0,sizeof(vis));        Dijastra(x,dis);        for(i=1;i<=n;i++)            dis2[i] = Mod;        dis2[x] = 0;        for(i=1;i<=n;i++)        {            for(j=i+1;j<=n;j++)            {                swap(mp[i][j],mp[j][i]);            }        }        memset(vis,0,sizeof(vis));        Dijastra(x,dis2);        int maxi = -1;        for(i=1;i<=n;i++)        {            if(dis[i] < Mod && dis2[i] < Mod)                maxi = max(maxi,dis[i]+dis2[i]);        }        printf("%d\n",maxi);    }    return 0;}
View Code

 


联系
我们