题面

Sol

巧妙的建图+\(Dijkstra\)

考虑把边看成点，那么显然暴力建图的边数是\(m^2\)的

考虑优化

把\(max(a, b)\)变成\(a+max(b-a,0)\)

把每个点连出的边按权值从小到大排序

每个边向后面的边连\(b-a\), 后面向前面连\(0\)

连向它的边向连出去的边连\(a\)

新建\(S\)点，向\(1\)连出的边连，新建\(T\)，连向\(n\)的边连\(T\)

没开long long WA一片

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(4e5 + 5);typedef int Arr[_]; IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;} Arr first, vis;ll dis[_];int n, m, cnt, S, T;struct Data{    int u; ll dis;     IL int operator <(RG Data B) const{        return dis > B.dis;    }};priority_queue 
      Q;struct Edge{    int to, next, w;} edge[_ << 2];struct Link{    int v, w, id;    IL int operator <(RG Link B) const{        return w < B.w;    }};vector 
       G[_];IL void Add(RG int u, RG int v, RG int w){    edge[cnt] = (Edge){v, first[u], w}, first[u] = cnt++;} IL void Dijkstra(){    Fill(dis, 63), dis[S] = 0, Q.push((Data){S, 0});    while(!Q.empty()){        RG Data x = Q.top(); Q.pop();        if(vis[x.u]) continue;        vis[x.u] = 1;        for(RG int e = first[x.u]; e != -1; e = edge[e].next){            RG int v = edge[e].to, w = edge[e].w;            if(dis[x.u] + w < dis[v]) Q.push((Data){v, dis[v] = dis[x.u] + w});        }    }} int main(RG int argc, RG char *argv[]){    Fill(first, -1), n = Input(), m = Input();    for(RG int i = 1; i <= m; ++i){        RG int u = Input(), v = Input(), w = Input();        G[u].push_back((Link){v, w, i});        G[v].push_back((Link){u, w, m + i});    }    T = m + m + 1; RG int tmp = m;    for(RG int i = 1; i <= n; ++i){        sort(G[i].begin(), G[i].end()); RG int l = G[i].size();        for(RG int j = 0; j < l; ++j){            Add((G[i][j].id > tmp ? G[i][j].id - m : G[i][j].id + m), G[i][j].id, G[i][j].w);            if(i == 1) Add(S, G[i][j].id, G[i][j].w);            if(G[i][j].v == n) Add(G[i][j].id, T, G[i][j].w);        }        for(RG int j = 0; j < l - 1; ++j){            Add(G[i][j].id, G[i][j + 1].id, G[i][j + 1].w - G[i][j].w);            Add(G[i][j + 1].id, G[i][j].id, 0);        }    }    Dijkstra();    printf("%lld\n", dis[T]);    return 0;}