2019 ICPC南京站网络赛 H题 Holy Grail（BF算法最短路）

计蒜客题目链接：https://nanti.jisuanke.com/t/41305

给定的起点是S，终点是T，反向跑一下就可以了，注意判负环以及每次查询需要添加边

AC代码：

#include<iostream>

#include<vector>

#include<queue>

#include<algorithm>

#include<cstring>

#define inf 0x3f3f3f3f

using namespace std;

struct node{

	vector<int> v;

	vector<int> w;

}g[305];

void addedge(int x,int y,int w){

	g[x].v.push_back(y);

	g[x].w.push_back(w);    //建图操作

}

int n,m;

int inq[305],cnt[305],d[305];

bool bellman_ford(int s,int t){

	queue<int> Q;

	memset(inq,0,sizeof(inq));

	memset(cnt,0,sizeof(cnt));

	memset(d,inf,sizeof(d));

	d[s] = 0;

	inq[s] = 1;

	Q.push(s);

	while(!Q.empty() ){

		int u = Q.front() ;

		Q.pop();

		inq[u] = 0;

		for(int i = 0;i<g[u].v.size() ;i++ ){

			int e = g[u].w[i];

			int v = g[u].v[i];

			if(d[u]<inf && d[v] > d[u] + e){

				d[v] = d[u] + e;

				if(!inq[v]){

					Q.push(v);

					inq[v] = 1;

					if(++cnt[v] > n){

						return false;//判定负环，若一个节点入队列超过n次则出现负环

					}

				}

			}

		}

	}

	return true;

}

int main(){

	int t;

	scanf("%d",&t);

	while(t--){

		scanf("%d%d",&n,&m);

		for(int i = 0;i<305;i++){

			g[i].v.clear() ,g[i].w.clear() ;  //清空图

		}

		for(int i = 1;i<=m;i++){

			int x,y,w;

			scanf("%d%d%d",&x,&y,&w);

			addedge(x,y,w);

		}

		for(int i = 0;i<6;i++){

			int s,t;

			scanf("%d%d",&s,&t);

			bellman_ford(t,s);

			printf("%d\n",-d[s]);

			addedge(s,t,-d[s]);//以题意在原图添加新的边

		}

	}

	return 0;

}

巴特西

2019 ICPC南京站网络赛 H题 Holy Grail（BF算法最短路）

最新文章

热门文章