http://poj.org/problem?id=3169
對(duì)于任意i號(hào)奶牛没佑，1<=i<N，在距離上應(yīng)該滿足：
D[i+1] - D[i] >= 0
對(duì)于每個(gè)好感的描述(i，j巷帝，k)匆笤，假設(shè)i<=j研侣，體現(xiàn)到距離上的要求就是：
D[j] - D[i] <= k
對(duì)于每個(gè)反感的描述(i，j炮捧，k)庶诡，假設(shè)i<=j，體現(xiàn)到距離上的要求就是：
D[j] - D[i] >= k
寫成我們約定的形式：
D[j] -D[i ]<= k
D[i] - D[j] <= - k
.對(duì)于差分不等式咆课，a - b <= c 末誓，建一條 b 到 a 的權(quán)值為 c 的邊扯俱，求的是最短路，得到的是最大值（本題求的就是最大值）喇澡，對(duì)于不等式 a - b >= c 迅栅，建一條 b 到 a 的權(quán)值為 c 的邊，求的是最長(zhǎng)路晴玖，得到的是最小值库继。
#include<cstdio>
#include<string.h>
using namespace std;
struct Node
{
int from,to,w;
}edge[20010];
int n,m,k,dis[1010],INF=0x3f3f3f3f;
void init()
{
memset(dis,INF,sizeof(dis));
dis[1]=0;
}
bool Bellman_Ford()
{
int sum=m+k;
bool flag;
for(int i=1;i<=n-1;i++)
{
flag=true;
for(int j=0;j<sum;j++)
{
int u=edge[j].from,v=edge[j].to,val=edge[j].w;
if(dis[v]>dis[u]+val)
{
dis[v]=dis[u]+val;
flag=false;
}
}
if(flag) break;
}
for(int j=0;j<sum;j++)
{
int u=edge[j].from,v=edge[j].to,val=edge[j].w;
if(dis[v]>dis[u]+val)
{
return true;
}
}
return false;
}
void reChange(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
int main()
{
int u,v,val,t;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
if(u>v) reChange(u,v);
edge[i].from=u;
edge[i].to=v;
edge[i].w=val;
}
for(int i=m;i<m+k;i++)
{
scanf("%d%d%d",&u,&v,&val);
if(u<v) reChange(u,v);
edge[i].from=u;
edge[i].to=v;
edge[i].w=-val;
}
init();
if(Bellman_Ford()) printf("-1\n");
else if(dis[n]==INF) printf("-2\n");
else printf("%d\n",dis[n]);
//printf("%d\n",INF);
}
