POJ 3159

• 题意：题目告诉我们求点1和点n之间在满足约束条件dist[a]+c>=dist[b]时的最大差值,
• 假设三角形abc,起点是a,a->b(2) a->c(4) b->c(3),当a点糖果数是0时,如果走a->b->c得到c糖果数为5,不满足a->c(4)的要求,所以转换为有向图,求最短路
• vector邻接表不行,用数组模拟邻接表

   #include <iostream>
  #include <string.h>
  #include <vector>
  #include <queue>
  using namespace std;
  const int maxn = 150005;
  int n,m;
  bool vis[maxn];
  int dist[maxn];
  
  int tot;
  int ver[maxn];
  int edge[maxn];
  int head[maxn];
  int next[maxn];
  
  void add(int x,int y,int z) {
  	ver[++tot] = y;edge[tot] = z;
  	next[tot] = head[x]; head[x] = tot;
  }
  
  void dij() {
  	memset(dist,0x3f,sizeof dist);
  	memset(vis,0,sizeof vis);
  	priority_queue<pair<int,int> > que;
  	dist[1] = 0;
  	que.push( make_pair(-dist[1],1) );
  	while (!que.empty()) {
  		int cur = que.top().second; que.pop();
  		if (vis[cur]) continue;
  		vis[cur] = 1;
  		for (int i = head[cur]; i; i=next[i]) { //扫描所有的出边,head[i]数组存的是点i的第一条边,
  			int to = ver[i];
  			int div = edge[i];
  			if (dist[to] > dist[cur] + div) {
  				dist[to] = dist[cur] + div;
  				que.push( make_pair(-dist[to],to) );
  			}
  		}
  	}
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	scanf("%d%d",&n,&m);
  	int u,v,w;
  	for (int i=1; i<=m; i++) {
  		scanf("%d%d%d",&u,&v,&w);
  		add(u,v,w);
  	}
  	dij();
  	cout << dist[n] << endl;
  	return 0;
  }