传送门: 【POJ】3169 Layout、【HDU】3592 World Exhibition
题目分析:我会说我只是凭直觉写的吗。。。。。。。
如果有B-A>=C形式的,则建边(B,A,-C)。
如果有B-A<=C形式的,则建边(A,B,C)。
对所有的点X,建边(X,X-1,0)。
最后跑一遍最短路。如果存在负环输出-1,如果点N不可达输出-2,否则输出点N的值(最短路径长度)。
是话说我也不知道为啥能AC,反正这样建图没错,起码我觉得挺对的= =...
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) const int MAXN = 1005 ; const int MAXE = 23333 ; const int INF = 0x3f3f3f3f ; struct Edge { int v , c ; Edge* next ; } E[MAXE] , *H[MAXN] , *cur ; int d[MAXN] ; int Q[MAXN] , head , tail ; bool inq[MAXN] ; int in[MAXN] ; int n , m1 , m2 ; void init () { cur = E ; CLR ( H , 0 ) ; } void addedge ( int u , int v , int c ) { cur -> v = v ; cur -> c = c ; cur -> next = H[u] ; H[u] = cur ++ ; } bool spfa () { CLR ( in , 0 ) ; CLR ( inq , 0 ) ; CLR ( d , INF ) ; head = tail = 0 ; Q[tail ++] = 1 ; d[1] = 0 ; while ( head != tail ) { int u = Q[head ++] ; if ( head == MAXN ) head = 0 ; inq[u] = 0 ; for ( Edge* e = H[u] ; e ; e = e -> next ) { int v = e -> v ; if ( d[v] > d[u] + e -> c ) { d[v] = d[u] + e -> c ; if ( !inq[v] ) { if ( ++ in[v] >= n ) return 0 ; inq[v] = 1 ; Q[tail ++] = v ; if ( tail == MAXN ) tail = 0 ; } } } } return 1 ; } void scanf ( int& x , char c = 0 ) { while ( ( c = getchar () ) < '0' || c > '9' ) ; x = c - '0' ; while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; } void solve () { int u , v , c ; init () ; FOR ( i , 2 , n ) addedge ( i , i - 1 , 0 ) ; while ( m1 -- ) { scanf ( u ) , scanf ( v ) , scanf ( c ) ; addedge ( u , v , c ) ; } while ( m2 -- ) { scanf ( u ) , scanf ( v ) , scanf ( c ) ; addedge ( v , u , -c ) ; } if ( spfa () ) printf ( "%d\n" , d[n] == INF ? -2 : d[n] ) ; else printf ( "-1\n" ) ; } int main () { while ( ~scanf ( "%d%d%d" , &n , &m1 , &m2 ) ) solve () ; return 0 ; }