题意：每行输入A、B、X 表示p[B] - p[A] >= X;求max( p[N] - p[1] )
思路：建图spfa+stack，一开始用的vecter做邻接表超时，用spfa+queue超时。改过后过了……
代码：
/*
poj 3159 查分约束
i j x 表示p[j] - p[i] >= x;
求max(p[n] - p[1])
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const int maxn = 30010;
const int maxv = 150010;
int size, head[maxn];
struct Edge{int to, dis, next;};
Edge edge[maxv];
int add_edge(int from, int to, int dis){
edge[size].to = to;
edge[size].dis = dis;
edge[size].next = head[from];
head[from] = size++;
}
bool vis[maxn];
int dis[maxn];
int n, m;
int spfa(int s, int t){
int res;
stack<int> dq;
memset(vis, 0, sizeof(vis));
fill(dis, dis+n+1, maxint);
dis[s] = 0;
dq.push(s);
while(dq.size()){
int fn = dq.front(); dq.pop();
vis[fn] = 0;
for(int i = head[fn]; i != -1; i = edge[i].next){
int to = edge[i].to;
int vel = edge[i].dis;
if( dis[to] > dis[fn] + vel) {
dis[to] = dis[fn] + vel;
if( !vis[to] ) {
vis[to] = 1;
dq.push(to);
}
}
}
}
return dis[t];
}
int main(){
// ios::sync_with_stdio(false);
int from, to, vel;
while(~scanf("%d%d",&n,&m)){
memset(head, -1, sizeof(head));
size = 0;
while(m--){
scanf("%d%d%d",&from,&to,&vel);
add_edge(from, to, vel);
}
spfa(1, n);
printf("%d\n",dis[n]);
}
return 0;
}