Contest1334/G.cpp

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define Max 1001
int cost[Max][Max];
int d[Max];
bool used[Max];
void dijkstra(int n,int s)    
{
    memset(d,INF,sizeof(d));
    memset(used,false,sizeof(used));
    d[s]=0;
    while(true)
    {
        int v=-1;
        for(int u=0;u<n;u++)
            if(!used[u]&&(v==-1||d[u]<d[v]))
                v=u;
        if(v==-1)
            break;
        used[v]=true;
        for(int u=0;u<n;u++)
        {
            d[u]=min(d[u],d[v]+cost[u][v]);
        }
    }
}
 
int main()
{
    int T,m,n,k,i,j;
    int from,to,Cost,f,t;
    //freopen("in.txt","r",stdin);
    cin>>T;
    while(T--)
    {
        memset(cost,INF,sizeof(cost));
        cin>>n>>m;
        for(i=0;i<m;i++)
        {
            cin>>from>>to>>Cost;
            cost[from][to]=cost[to][from]=Cost;
        }
        cin>>f>>t;
        dijkstra(n,f);
        int Time[Max],tim=0;
        memset(Time,0,sizeof(Time));
        for(i=0;i<n;i++)
            Time[i]=d[i];
        dijkstra(n,t);
        for(i=0;i<n;i++)
        {
            Time[i]+=d[i];
            tim=max(tim,Time[i]);
        }
        cout<<tim<<endl;
 
    }
}