直接差分约束求最短路 - c++编程基础

    临行前最后一题，居然还不给我1A.题意，给出一堆B-A<=C,问1和N这两人的最大差值。直接差分约束求最短路，即最大值即可。初值将1设为0,那么最大差值就是dis[n],AC. 但是这道题居然卡SPFA,太神奇了。然后要DIJ+HEAP才可以。看了DISCUSS说，SPFA把队列改成栈就能过，真是神奇。
    01.#include <set>
    02.#include <map>
    03.#include <stack>
    04.#include <cmath>
    05.#include <queue>
    06.#include <cstdio>
    07.#include <string>
    08.#include <vector>
    09.#include <iomanip>
    10.#include <cstring>
    11.#include <iostream>
    12.#include <algorithm>
    13.#define Max 2505
    14.#define FI first
    15.#define SE second
    16.#define ll long long
    17.#define PI acos（-1.0）
    18.#define inf 0x3fffffff
    19.#define LL（x）（ x 《 1 ）
    20.#define bug puts（"here"）
    21.#define PII pair<int,int>
    22.#define RR（x）（ x 《 1 | 1 ）
    23.#define mp（a,b） make_pair（a,b）
    24.#define mem（a,b） memset（a,b,sizeof（a））
    25.#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
    26.
    27.using namespace std;
    28.
    29.#define M 999999
    30.#define N 111111
    31.int n , m ;
    32.struct kdq {
    33.    int e , l , next ;
    34.} ed[M] ;
    35.int head[N] , num ;
    36.void init（） {
    37.    mem（head ,-1） ;
    38.    num = 0 ;
    39.}
    40.void add（int s ,int e ,int l） {
    41.    ed[num].e = e ;
    42.    ed[num].l = l ;
    43.    ed[num].next = head[s] ;
    44.    head[s] = num ++ ;
    45.}
    46.int dis[N] , cnt[N] ;
    47.bool vis[N] ;
    48.queue<int>qe ;
    49.int spfa（） {
    50.    while（！qe.empty（））qe.pop（） ;
    51.    for （int i = 0 ; i <= n ; i ++ ）dis[i] = inf ,cnt[i] = 0 ;
    52.    dis = 0 ;
    53.    mem（vis ,0） ;
    54.    qe.push（1） ;
    55.    vis = 1 ;
    56.    while（！qe.empty（）） {
    57.        int tp = qe.front（） ;
    58.        qe.pop（） ;
    59.        vis[tp] = 0 ;
    60.        if（cnt[tp] > n）return -1 ;

    61.        for （int i = head[tp] ; ~i ; i = ed[i].next ） {
    62.            int e = ed[i].e ;
    63.            int l = ed[i].l ;
    64.            if（dis[e] > dis[tp] + l） {
    65.                dis[e] = dis[tp] + l ;
    66.                if（！vis[e]） {
    67.                    vis[e] = 1 ;
    68.                    qe.push（e） ;
    69.                    cnt[e] ++ ;
    70.                }
    71.            }
    72.        }
    73.    }
    74.    return dis[n] - dis ;
    75.}
    76.
    77.struct DIJ {
    78.    int e , l ;
    79.    DIJ（） {}
    80.    DIJ（int ee , int lx）：e（ee） , l（lx） {}
    81.    bool operator < （const DIJ &fk ）const {
    82.        return l > fk.l ;
    83.    }
    84.} ;
    85.//queue<DIJ>q ;
    86.int dij（） {
    87.    priority_queue<DIJ>q ;
    88.    for （int i = 1 ; i <= n ; i ++ ）dis[i] = inf ;
    89.    mem（vis ,0） ;
    90.    dis = 0 ;
    91.    q.push（（DIJ） {
    92.        1 , 0
    93.    }） ;
    94.    while（！q.empty（）） {
    95.        DIJ tp = q.top（） ;
    96.        q.pop（） ;
    97.        if（vis[tp.e]）continue ;
    98.        vis[tp.e] = 1 ;
    99.        for （int i = head[tp.e] ; ~i ; i = ed[i].next ） {
    100.            int e = ed[i].e ;
    101.            int l = ed[i].l ;
    102.            if（dis[e] > dis[tp.e] + l ） {
    103.                dis[e] = dis[tp.e] + l ;
    104.                q.push（DIJ（e , dis[e]）） ;
    105.            }
    106.        }
    107.    }
    108.    return dis[n] ;
    109.}
    110.int main（） {
    111.    while（cin 》 n 》 m ） {
    112.        int a , b , c ;
    113.        init（） ;
    114.        for （int i = 0 ; i < m ; i ++ ） {
    115.            scanf（"%d%d%d",&a,&b,&c） ;
    116.            add（a , b , c） ;
    117.        }
    118.        printf（"%d\n",dij（）） ;
    119.    }
    120.    return 0 ;
    121.}