H. Holy Grail（The Preliminary Contest for ICPC Asia Nanjing 2019题解）

题目链接As the current heir of a wizarding family with a long history,unfortunately, you find yourself forced to participate in the cruel Holy Grail War which has a reincarnation of sixty years.However,fortunately,you summoned a Caster Servant with a powerful Noble Phantasm.When your servant launch her Noble Phantasm,it will construct a magic field,which is actually adirectedgraphconsisting ofn verticesandm edges.More specifically,the graph satisfies the following restrictions :Does not have multiple edges(for each pair of verticesxandy, there is at most one edge between this pair of vertices in the graph) and does not have self-loops(edges connecting the vertex with itself).May havenegative-weighted edges.Does not have anegative-weighted loop.n300,m500.Currently,as your servants Master,as long as you add extra6edges to the graph,you will beat the other 6 masters to win the Holy Grail.Howeveryou are subject to the following restrictions when you add the edges to the graph:Each time you add an edge whose cost is c,it will cost you c units of Magic Value.Therefore,you need to add an edge which has the lowest weight(its probably that you need to add an edge which has a negative weight).Each time you add an edge to the graph,the graph must not have negative loops,otherwise you will be engulfed by the Holy Grail you summon.InputInput data contains multiple test cases. The first line of input contains integert— the number of testcases (1≤t≤5).For each test case,the first line contains two integers n,m,the number of vertices in the graph, the initial number of edges in the graph.Then m lines follow, each line contains three integersx, y and w(0≤x,yn,-10^9≤w≤10^9, x​y) denoting an edge from vertices x to y (0-indexed) of weight w.Then 6 lines follow, each line contains two integerss,tdenotingthe starting vertexandthe ending vertexof the edge you need to add to the graph.It is guaranteed that there is not an edge starting froms to tbefore you add any edges and there must exists such an edge which has the lowest weight and satisfies the above restrictions, meaning the solution absolutely exists for each query.OutputFor each test case,output 666 lines.Each line contains the weight of the edge you add to the graph.INPUT 1 10 15 4 7 10 7 6 3 5 3 3 1 4 11 0 6 20 9 8 25 3 0 9 1 2 15 9 0 27 5 2 0 7 3 -5 1 7 21 5 0 1 9 3 16 1 8 4 4 1 0 3 6 9 2 1 8 7 0 4 OUTPUT -11 -9 -45 -15 17 7题意n个点m条边给出m条边的起点终点和权值最后给出6组数x,y要求在x到y上加权值问所加权值最小为多少加边满足加完之后不能有负环加完立即生效。思路直接找y到x的最短路取相反值即可因为这样不会有负环。因为有负边所以用SPFA。#includestdio.h #includealgorithm #includeiostream #includeset #includemap #includestring #includestring.h #includemath.h #includevector #includequeue #define maxn 150000 #define ll long long #define inf 0x3f3f3f3f using namespace std; ll dis[500]; int vis[500]; struct A { int to; ll w; }; vector A v[500]; void SPFA(ll s) { queue int q; memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]0; vis[s]1; q.push(s); while(!q.empty()) { int uq.front(); q.pop(); vis[u]0; for(int i0;iv[u].size();i) { int xv[u][i].to; ll yv[u][i].w; if(dis[u]ydis[x]) { dis[x]dis[u]y; if(vis[x]0) { q.push(x); vis[x]1; } } } } return ; } int main() { int t; scanf(%d,t); while(t--){ int n,m,a,b; ll c; struct A t; scanf(%d%d,n,m); for(int i1;im;i){ scanf(%d %d %lld,a,b,c); t.to b; t.w c; v[a].push_back(t); } for(int i0;i6;i){ scanf(%d %d,a,b); SPFA(b); ll ans dis[a]; t.to b; t.w (-1)*ans; v[a].push_back(t); printf(%lld\n,(-1)*ans); } for(int i0;in;i){ v[i].clear(); } } return 0; }