大家好，又见面了，我是全栈君。
题目链接：http://poj.org/problem?id=3159
题意：给出m给 x 与y的关系。当中y的糖数不能比x的多c个。即y-x <= c 最后求fly[n]最多能比so[1] 多多少糖？
差分约束问题， 就是求1-n的最短路， 队列实现spfa 会超时了，改为栈实现，就可以
有负环时，用栈比队列快
数组开小了，不报RE，报超时 ，我晕
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
const int N = 210;
const int maxn = 30100;
const int maxm = 200000;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define init(a) memset(a,0,sizeof(a))
#define MIN INT_MIN
#define MAX INT_MAX
#define LL long long
using namespace std;
int max(int a,int b){if(a>b)return a; else return b;}
int min(int a,int b){if(a<b)return a; else return b;}
const int INF=0x3f3f3f3f;
struct node
{
int v,w;
int next;
}edge[maxm];
int head[maxn];
bool vis[maxn];
int dis[maxn];
int cnt;
void add(int a,int b,int w)//加边
{
edge[cnt].v=b;
edge[cnt].w=w;
edge[cnt].next=head[a];
head[a]=cnt++;
}
void SPFA(int s,int n)
{
//stack<int>stk;
int stk[100000];
int top = 0;
//stk.push(s);
stk[top++] = s;
FOR(i,1,n+1)
{dis[i] = INF;
vis[i] = 0;
}
dis[s] = 0;
vis[s] = 1;
while(top!=0)
{
int u=stk[--top];
//stk.pop();
vis[u]=false;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!vis[v])
{
vis[v]=true;
stk[top++] = v;
}
}
}
}
}
void initt()
{
cnt=0;
memset(head,-1,sizeof(head));
}
int main()
{
int n,m;
int a,b,c;
while(scanf("%d%d",&n,&m)!=EOF)
{
initt();
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
SPFA(1,n);
printf("%d\n",dis[n]);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115400.html原文链接：https://javaforall.net
