Holy Grail

Holy Grail

题意：

• 有一个顶点数为n,边数为m的有向图， 图中可能有负权值，但是没有负加权循环
  要求在6组点S与点T之间加上一条边，这条边要尽可能的短，且图中不能出现负循环

思路：

• 对于题目中给定的任意一个点对 S、T ，记要添加的有向边 的权值为 。显然，当 时， 即为我们要求的解，其中 为从 T 到 S 的最短路径长度取反后的值。
  注意：每次找出一组边的最小值，原图中就多了一条边，所以注意加上添加的边

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int dis[330];
int edge[330][330];
int vis[330];
int n,m;
void spfa(int x)
{
    memset(vis,0,sizeof(vis));
    memset(dis,INF,sizeof(dis));
    queue<int>qu;
    qu.push(x);
    dis[x]=0;
    vis[x]=1;
    while(!qu.empty( ))
    {
        int u=qu.front( );
        qu.pop( );
        vis[u]=0;
        for(int i=0; i<n; i++)
        {
            if(dis[i]>dis[u]+edge[u][i])
            {
                dis[i]=dis[u]+edge[u][i];
                if(!vis[i])
                {
                    qu.push(i);
                    vis[i]=1;
                }
            }
        }
    }
}
int main( )
{
    int t,x,y,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(edge,INF,sizeof(edge));
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            edge[x][y]=w;
        }
        for(int i=1; i<=6; i++)
        {
            scanf("%d%d",&x,&y);
            spfa(y);
            printf("%d\n",-dis[x]);
            edge[x][y]=-dis[x];
        }
    }
    return 0;
}