poj Layout 差分约束+SPFA

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

很好的差分约束入门题目,自己刚看时学呢

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 1010
int dis[maxn];
int path[maxn];
int inq[maxn];
int cnt[maxn];
class node
{
public:
int to;
int w;
int next;
};
node edge[maxn*];
int head[maxn*];
int tol;
int n,ML,MD;
void add(int u,int v,int w)
{
edge[tol].to=v;
edge[tol].w =w;
edge[tol].next=head[u];
head[u]=tol++;
};
queue<int>Q;
bool SPFA()
{
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt));
int v0=;
for(int i=;i<=n;i++)
{
dis[i]=INF;
path[i]=v0;
inq[i]=;
}
dis[v0]=;
path[v0]=v0;
inq[v0]++;
cnt[v0]++;
Q.push(v0);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
inq[u]--;
int tmp=head[u]; while(tmp!=-)
{
int v=edge[tmp].to;
int w=edge[tmp].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
path[v]=u;
if(inq[v]==)
{
inq[v]++;
if(++cnt[v]>n) return false;
Q.push(v); }
}
tmp=edge[tmp].next;
}
}
return true;
}
int main()
{
int a,b,d;
while(scanf("%d%d%d",&n,&ML,&MD)!=EOF)
{
tol=;
memset(head,-,sizeof(head));
while(ML--)
{
scanf("%d%d%d",&a,&b,&d);
add(a,b,d); }
while(MD--)
{
scanf("%d%d%d",&a,&b,&d);
add(b,a,-d);
}
if(!SPFA()) cout<<"-1"<<endl;
else
if(dis[n]>=INF) cout<<"-2"<<endl;
else cout<<dis[n]<<endl; }
return ;
}
上一篇:CS50.5


下一篇:(简单) POJ 3169 Layout,差分约束+SPFA。