原题地址

其实这个题目思考起来和实现起来并不难 ，但是为了码一下发现的dalao的博客，还是写一下题解

dalao博客：
夜深人静写算法（四） - 差分约束

真的写的非常好啊！可以说是帮我又把最短路和建图的知识复习了一遍，吹爆dalao，简单的逛了一下，他其他的文章包括ｄｐ、线段树、树状数组等等都写的非常认真非常仔细，还附题集，每一题还点出了重点是什么，可以说是非常良心了！决定了，以后就跟着这个dalao混了！

思路

首先，差分约束这个东西听起来很高深，但实际上逻辑非常友好，处理一组不等式，求最大最小值，最大值会被其他比较小的最大值约束，最小值会被其他比较大的最小值约束，最后统统可以转换为求最短路/最长路的问题，这就是差分约束的关键。本题中给了ｍ条边，要求求第１个节点到第ｎ个节点的最大值，这个最大值实际上是求ｎ到１的最短路，也就是被约束住了，这么样去想，就很容易明白了。
当然，差分约束的应用并没有那么简单，想要用好还是要多多练习的。
顺便，这个题目听说想要不TLE，必须用堆优化的dijkstra，或者用栈优化的spfa，这就很玄学了，好像是说栈队列优化的spfa并没有相差很多，但是这个题目如果用队列就超时，很奇怪。
（另外：链式前向星很好的一点是不会爆内存，而且存权值很方便，如果用邻接表有时候很难存下一大组数据，写的时候也很没底的，这个一定要掌握。）

spfa + stack:

#include <iostream>
#include <stack>
#include <utility>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const static int maxn = 30010;
typedef pair<int, int> pii;
bool vis[maxn];
int d[maxn];
int n, m, len;
int head[maxn];
struct edge
{
    int v, w;
    int next;
}e[150010];
void add(int u, int v, int w)
{
    e[len].v = v;
    e[len].w = w;
    e[len].next = head[u];
    head[u] = len++;
}
void spfa(int x)
{
    stack <int> s;
    s.push(x);
    d[x] = 0;
    vis[x] = true;
    while(!s.empty())
    {
        int u = s.top();
        s.pop();
        vis[u] = false;
        for(int i=head[u]; i!=-1; i = e[i].next)
        {
            int v = e[i].v;
            if(d[v] > d[u] + e[i].w)
            {
                d[v] = d[u] + e[i].w;
                if(!vis[v])
                {
                    s.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        d[i] = inf;
        head[i] = -1;
        vis[i] = false;
    }
    for(int i=1; i<=m; i++)
    {
        int a, b, w;
        scanf("%d %d %d",&a, &b, &w);
        add(a, b, w);
    }
    spfa(1);
    printf("%d", d[n]);
    return 0;
}

dijkstra + priority_queue:

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const static int maxn = 30010;
typedef pair<int, int> pii;
bool vis[maxn];
int d[maxn];
int n, m, len;
int head[maxn];
struct edge
{
    int v, w;
    int next;
}e[150010];
void add(int u, int v, int w)
{
    e[len].v = v;
    e[len].w = w;
    e[len].next = head[u];
    head[u] = len++;
}
void dijstra(int x)
{
    priority_queue<pii, vector<pii>, greater<pii> > q;
    d[x] = 0;
    q.push(make_pair(d[x], x));
    while(!q.empty())
    {
        pii temp = q.top();
        q.pop();
        int u = temp.second;
        if(vis[u])
            continue;
        vis[u] = true;
        for(int i=head[u]; i!=-1; i = e[i].next)
        {
            int v = e[i].v;
            if(d[v] > d[u] + e[i].w && !vis[v])
            {
                d[v] = d[u] + e[i].w;
                q.push(make_pair(d[v], v));
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        d[i] = inf;
        head[i] = -1;
        vis[i] = false;
    }
    for(int i=1; i<=m; i++)
    {
        int a, b, w;
        scanf("%d %d %d",&a, &b, &w);
        add(a, b, w);
    }
    dijstra(1);
    printf("%d", d[n]);
    return 0;
}