H - Holy Grail_牛客博客

题意：

题干又臭又长
我简单说说
n个点，m条有向边，边权为负，然后给你六组起始点（s点和t点），你要在s和t之间建一个有向边，要使得权值最小，问这六组边依次是多少？
不能形成负循环
（可以添加负边，题目给的边权也有可能为负）

题解：

既然可以添加负边，那就是边权越小越好，但是不能形成负循环，想想我们要从s到t建一个边，假如说t到s的最短路是w，那我们能建的边就是-w，这样两者抵消为0，正好不是负循环，这就是最佳情况
也就是我们从t开始跑最短路，求到s的最短路径w，然后我们添加的边权是-w.
注意这个w不一定是正的，也有可能是负的，为了不形成负循环，我们就要添加正边权，所以添加的边权取决于w的符号（与w相反）
这个题有好多注意的点：

n个点，点的序号是从0 ~ n-1 （一开始我一直wa就是忘了第0点）
最短路记得跑spfa，因为有负边权
每次求出一组答案，记得将答案更新到图中，也就是建立s->t,边权为你求出的值，因为后面的组有可能会用到这个边
t组数据，所以记得及时清零数组
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{
  int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码，不懂翻书看解释
  edge[++num_edge].next=head[from]; //链式存储下一条出边
  edge[num_edge].to=to; //当前节点编号
  edge[num_edge].dis=dis; //本条边的距离
  head[from]=num_edge; //记录下一次的出边情况
}
void spfa()
{

  queue<int> q; //spfa用队列，这里用了STL的标准队列
  for(int i=1; i<=n; i++) 
  {
    dis[i]=inf; //带权图初始化
    vis[i]=0; //记录点i是否在队列中，同dijkstra算法中的visited数组
  }
  q.push(s);
  dis[s]=0;
  vis[s]=1; //第一个顶点入队，进行标记
  while(!q.empty())
  {
    int u=q.front(); //取出队首
    q.pop();
    vis[u]=0; //出队标记
    for(int i=head[u]; i; i=edge[i].next) //邻接表遍历，不多解释了（也可用vector代替）
    {
      int v=edge[i].to; 
      if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
      {
        dis[v]=dis[u]+edge[i].dis;
        if(vis[v]==0) //未入队则入队
        {
          vis[v]=1; //标记入队
          q.push(v);
        }
      }
    }
  }
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        memset(edge,0,sizeof(edge));
        memset(head,0,sizeof(head));
        num_edge=0;
        cin>>n>>m;

          for(int i=1; i<=m; i++)
          {
            int u,v,w;
            cin>>u>>v>>w;
            if(u==0)u=n;
            if(v==0)v=n;
            addedge(u,v,w);
          }
          for(int i=1;i<=6;i++)
          {
              int u,v;
              cin>>u>>v;
              if(u==0)u=n;
            if(v==0)v=n;
              s=v;
            spfa(); //开始跑spfa
            cout<<(-1)*dis[u]<<endl;
            addedge(u,v,(-1)*dis[u]);
          }


    }

  return 0;
}

H - Holy Grail

题意：

题解：

代码：