LightOJ 1074 Extended Traffic(The shortest path)

Description

给出n个点的权值(不超过20),点 i 到点 j 之间的距离(如果可达)为(a[j] - a[i]) ^ 3,求到查询点的最短路径

Analyze

单向边，可有负权边，可含负权环 -> 用spfa叭

若某个点在负权环里(++times[to] > n)，那么从点to出发所能到达的点(无论是否在负权环里)到起点的距离都是无限小，可以DFS枚举所有可达点并标记

（补充一下：若是单纯求负权环上所有点，应该与强连通分量有关，不仅仅是DFS这么简单）

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 205;
const int INF = 0x3f3f3f3f;

int n, val[MAX_N];

struct edge
{
    int to, w, pre;
} e[50005];

int cnt, head[50005], dis[MAX_N], vis[MAX_N], times[MAX_N], through_circle[MAX_N];

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
        head[i] = -1, dis[i] = INF, vis[i] = 0, times[i] = 0, through_circle[i] = 0;
}

void add(int from, int to, int w)
{
    e[cnt].to = to;
    e[cnt].w = w;
    e[cnt].pre = head[from];
    head[from] = cnt++;
}

///这些点不仅是负环上的点，还有不在负环上但最短路经由负环的点!
void DFS(int now)
{
    through_circle[now] = 1;
    for(int i = head[now]; ~i; i = e[i].pre)
        if(!through_circle[ e[i].to ])
            DFS(e[i].to);
}

void spfa()
{
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = 1, times[1] = 1;
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(int i = head[now]; ~i; i = e[i].pre)
        {
            int to = e[i].to;
            if(dis[to] > dis[now] + e[i].w)
            {
                dis[to] = dis[now] + e[i].w;
                if(!through_circle[to] && !vis[to])
                    q.push(to), vis[to] = 1;
                if(++times[to] > n)
                    DFS(to);
            }
        }
    }
}

int main()
{
    int _, tot = 1;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d", &n);
        init();
        for(int i = 1; i <= n; ++i)
            scanf("%d", &val[i]);
        int num, u, v, w;
        scanf("%d", &num);
        for(int i = 0; i < num; ++i)
        {
            scanf("%d %d", &u, &v);
            w = (val[v] - val[u])*(val[v] - val[u])*(val[v] - val[u]);
            add(u, v, w);
        }
//        Dijkstra();
        spfa();

        int q;
        cout << "Case " << tot++ << ":\n";
        scanf("%d", &num);
        while(num--)
        {
            scanf("%d", &q);
            ///cout << (dis[q] <= 3 ? '?' : dis[q]) << '\n';
            if(dis[q] < 3 || dis[q] == INF || through_circle[q] == 1)
                cout << '?' << '\n';
            else
                cout << dis[q] << '\n';
        }
    }
    return 0;
}
Copy
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

补充：三目运算符后面两者的类型需要一致

dis[q] <= 3 ? '?' : dis[q]

以上代码该输出’?’的时候输出了63(?的ASCLL码)