3169:Layout
問題文
http://poj.org/problem?id=3169
蟻本で解説されてる問題。やっと理解した。
不等式制約の双対をとると最短経路問題になる。
#include <iostream> #include <vector> #include <algorithm> #define MAX_V 1001 #define MAX_E 30000 #define INF (1<<29) using namespace std; struct edge{int from,to,cost;}; vector<edge> es; int d[MAX_V],n; void shortest_path(int s){ for(int i=0;i<n;i++)d[i]=INF; d[s]=0; for(int k=0;k<n;k++){ bool update=false; for(int i=0;i<es.size();i++){ edge e=es[i]; if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost){ d[e.to]=d[e.from]+e.cost; update=true; } } if(!update)break; } } int main(void){ int ml,md; cin >> n >> ml >> md; for(int i=0;i<n-1;i++){ es.push_back((edge){i+1,i,0}); } for(int i=0;i<ml;i++){ int a,b,d; cin >> a >> b >> d; es.push_back((edge){a-1,b-1,d}); } for(int i=0;i<md;i++){ int a,b,d; cin >> a >> b >> d; es.push_back((edge){b-1,a-1,-d}); } shortest_path(0); if(d[n-1]==INF)cout << -2 << endl; else if(d[0]<0)cout << -1 << endl; else cout << d[n-1] << endl; return 0; }