POJ3159 (Candies)[差分约束，栈SPFA]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=3159

这题是裸的差分约束，但是直接使用队列SPFA会超时，使用栈SPFA才能过。。还不是特别理解

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=30009;
const int maxm=150009;
const long long inf=10000000000000000LL;
typedef long long ll;
int head[maxn];
int ver[maxm];
int next[maxm];
int e[maxm];
int tot=1;
bool vis[maxn];
ll d[maxn];
int n,m;
int s;
int q[10000000],top;

void add(int u,int v,int w) {
    ver[++tot]=v;e[tot]=w;next[tot]=head[u];head[u]=tot;
}
void spfa() {
    //queue<int> q;
    for(int i=1;i<=n;i++) d[i]=inf;
    //q.push(s);
    top=0;
    q[++top]=s;
    vis[s]=1;
    d[s]=0;
    int now;
    while(top>0) {
        //int now=q.front(); q.pop();
        now=q[top--];
        for(int i=head[now],v;i;i=next[i]) {
            v=ver[i];
            if(d[now]+e[i]<d[v]) {
                d[v]=d[now]+e[i];
                if(!vis[v]) {
                    vis[v]=1;
                    //q.push(v);
                    q[++top]=v;
                    //r=(r+1)%MOD;
                }
            }
        }
        vis[now]=0;
    }
}
inline int read() {
    char ch=getchar();
    int ans=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans;
}
int main() {
    int a,b,c;
    //scanf("%d%d",&n,&m);
    n=read();
    m=read();
    for(int i=0;i<m;i++) {
        //scanf("%d%d%d",&a,&b,&c);
        a=read();
        b=read();
        c=read();
         //printf("%d %d %d\n",a,b,c);
        add(a,b,c);
    }
    s=1;
    spfa();
    printf("%I64d",d[n]);
}