2019ACM-ICPC南京网络赛Holy Grail （SPFA / Floyd 模板题）

冷不防 2023-06-05 12:33 22阅读 0赞

**Holy Grail**

**限制**

1000 ms

256 MB

As the current heir of a wizarding family with a long history,unfortunately, you fifind 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

fifield,which is actually a directed graph consisting of n vertices and m edges.More

specififically,the graph satisfifies the following restrictions :

Does not have multiple edges(for each pair of vertices x and y, 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 have negative-weighted edges.

Does not have a negative-weighted loop.

n<=300 , m<=500.

Currently,as your servant's Master,as long as you add extra 6 edges to the graph,you will

beat the other 6 masters to win the Holy Grail.

However，you 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(it's 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.

**Input**

Input data contains multiple test cases. The fifirst line of input contains integer t — the

number of test

cases (1 ≤ t ≤ 5).

For each test case,the fifirst 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 integers x, y and w (0 ≤ x, y < n,−109≤w≤

109, x = y) denoting an edge from vertices x to y (0-indexed) of weight w.Then 6 lines follow, each line contains two integers s,t denoting the starting vertex and

the ending vertex of the edge you need to add to the graph.

It is guaranteed that there is not an edge starting from s to t before you add any edges and

there must exists such an edge which has the lowest weight and satisfifies the above

restrictions, meaning the solution absolutely exists for each query.

**Output**

For each test case,output 6 lines.

Each line contains the weight of the edge you add to the graph.

**Sample Input**

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

**Sample Output-11**

\-9

\-45

\-15

**比赛时用的SPFA,其实用Floyd也可以做，泪奔，awsl。。。。。。。。。。。。。。。。**

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn=3e2+7,maxm=5e2+5;
     5 const ll inf=1e16;
     6 int head[maxm],vis[maxn],cnt=0;
     7 ll dist[maxn];
     8 struct node
     9 {
    10     int to,next;
    11     ll w;
    12 } edge[maxm];
    13 void add(int a,int b,ll w)
    14 {
    15     edge[++cnt].to=b,edge[cnt].next=head[a];
    16     edge[cnt].w=w,head[a]=cnt;
    17 }
    18 queue<int>que;
    19 void spfa(int t)
    20 {
    21     dist[t]=0,vis[t]=1;
    22     que.push(t);
    23     while(que.size())
    24     {
    25         int now=que.front();
    26         que.pop();
    27         vis[now]=0;
    28         for(int i=head[now]; i; i=edge[i].next)
    29         {
    30             int to=edge[i].to,w=edge[i].w;
    31             if(dist[to]>dist[now]+w)
    32             {
    33                 dist[to]=dist[now]+w;
    34                 if(!vis[to])
    35                 {
    36                     que.push(to);
    37                     vis[to]=1;
    38                 }
    39             }
    40         }
    41     }
    42 }
    43 int main()
    44 {
    45     int t;
    46     scanf("%d",&t);
    47     while(t--)
    48     {
    49         cnt=0;
    50         memset(vis,0,sizeof(vis));
    51         memset(head,0,sizeof(head));
    52         for(int i=0; i<=maxn-2; ++i)
    53             dist[i]=inf;
    54         int n,m,a,b,s,t;
    55         ll w;
    56         scanf("%d%d",&n,&m);
    57         for(int i=1; i<=m; ++i)
    58         {
    59             scanf("%d %d %lld",&a,&b,&w);
    60             add(a,b,w);
    61         }
    62         for(int i=1; i<=6; ++i)
    63         {
    64             scanf("%d %d",&s,&t);
    65             spfa(t);
    66             printf("%lld\n",-dist[s]);
    67             add(s,t,-dist[s]);
    68             memset(vis,0,sizeof(vis));
    69             for(int i=0; i<=maxn-2; ++i)
    70                 dist[i]=inf;
    71         }
    72     }
    73     return 0;
    74 }

转载于:https://www.cnblogs.com/CharlieWade/p/11443389.html