MYF

PKU Campus G Challenge Your Template

Posted on | In | | Visitors

题目链接

C16G:Challenge Your Template
SPFA求最短路

题目分析

题目大意

给出一个加边的程序，让你求所生成图形的最短路。

解析

SPFA直接加板子就能过，但是Dijkstra会挂掉

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
#define inf 9999
#define Vmax 1000005
#define Emax 4000005
int pre[Vmax],ecnt;
struct edge{
    int v,w,next;
}e[Emax*2];
int dis[Vmax];
int vcnt[Vmax];//记录每个点进队次数，用于判断是否出现负环
bool inq[Vmax];
void init(){
    ecnt=0;
    memset(vcnt,0,sizeof(vcnt));
    memset(pre,-1,sizeof(pre));
    memset(inq, false, sizeof(inq));
}
//***注意双向加边
void adde(int from,int to,int w){
    
    //减边
    for (int i=pre[from]; i!=-1; i=e[i].next) {
        if (e[i].v==to) {
            e[i].w=min(e[i].w, w);
            return;
        }
    }
    
    e[ecnt].v=to;
    e[ecnt].w=w;
    e[ecnt].next=pre[from];
    pre[from]=ecnt++;
}
bool SPFA(int n,int source){//n为顶点数 source为起点
    //return true表示无负环，反之亦然
    for (int i=0; i<=n; i++)
        dis[i]=inf;
    dis[source]=0;
    queue<int>q;
    q.push(source);inq[source]=true;
    
    while (!q.empty()) {
        int tmp=q.front();
        q.pop();inq[tmp]=false;
        
        //判断负环
        vcnt[tmp]++;
        if (vcnt[tmp]>=n) return false;
        
        for (int i=pre[tmp]; i!=-1; i=e[i].next) {
            int w=e[i].w;
            int v=e[i].v;
            if (dis[tmp]+w<dis[v]) {
                dis[v]=dis[tmp]+w;  //松弛操作
                if (!inq[v]) {
                    q.push(v);
                    inq[v]=true;
                }
            }
        }
    }
    return true;
}
int get_ans(int n,int source,int destination){
    SPFA(n,source);
    return dis[destination];
}
void buildGraph(int N, int Seed) {
    int nextRand = Seed;
    // initialize random number generator
    for (int x = 1; x <= N; x++) {
        // generate edges from Node x
        int w = x % 10 + 1;            // the weight of edges
        int d = 10 - w;                // the number of edges
        for (int i = 1; i <= d; i++) {
            adde(x, nextRand % N + 1, w);
            // add a new edge into G
            nextRand = nextRand * 233 % N;
        }
        adde(x, x % N + 1, w);
    }
}
int main(){
    int t,n,s;
    cin>>t;
    while (t--) {
        cin>>n>>s;
        init();
        buildGraph(n, s);
        cout<<get_ans(n,1,n)<<endl;
    }
    return 0;
}