首页 > 代码库 > 差分约束Poj3159 Candies

差分约束Poj3159 Candies

2024-07-07 04:31:08   231人阅读

没负环。直接搞就行，但是 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
int n;
using namespace std;
struct edge
{
    int to;int val;int next;
}e[555555];
 
int len;int head[33333];
 
void add(int from ,int to,int val)
{
    e[len].to=to;e[len].val=val;
    e[len].next=head[from];head[from]=len++;
}
 
const int INF=0xfffffff;
int dis[44444];
void spfa(int x)
{
    int vis[444444];
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[x]=0; vis[x]=1;
    stack<int> q;// 不知道为什么 栈能过  队列却不行。
    q.push(x);
    while(!q.empty()){
        int cur=q.top();vis[cur]=0;q.pop();
        for(int i= head[cur];i!=-1;i=e[i].next){
            int cc=e[i].to;
            if(dis[cc]>dis[cur]+e[i].val){
                dis[cc]=dis[cur]+e[i].val;
                if(!vis[cc]){
                    vis[cc]=1;
                    q.push(cc);
                }
            }
        }
    }
}
 
int main()
{
    int m;
    scanf("%d%d",&n,&m);
        len=0;memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++){
            int a,c,b;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        spfa(1);
        printf("%d\n",dis[n]);
    return 0;
}

　　


联系
我们