D68 最短路+边拆点 Dijkstra 算法

// 最短路+边拆点 Dijkstra 算法 O(mlogn)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N=400010;
vector<pii> e[N],ee[N];
int n,m,cnt,d[N],vis[N];

void dijkstra(int s){
  memset(d,0x3f,sizeof d);
  priority_queue<pii,vector<pii>,greater<pii>> q;
  q.emplace(d[s]=0,s);
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(vis[u]) continue;
    vis[u]=1;
    for(auto [w,v]:ee[u]){
      if(d[v]>d[u]+w) q.emplace(d[v]=d[u]+w,v);
    }
  }
}
signed main(){
  ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1,u,v,w; i<=m; i++){
    cin>>u>>v>>w;
    e[u].emplace_back(w,cnt++); //点u的出边点cnt
    e[v].emplace_back(w,cnt++); //点v的出边点cnt
  }
  int s=cnt,t=cnt+1;
  for(int i=1; i<=n; i++){
    sort(e[i].begin(),e[i].end()); //对i点的出边排序
    for(int j=0; j<e[i].size(); j++){
      int v1=e[i][j].second,w1=e[i][j].first,
          v2=e[i][j+1].second,w2=e[i][j+1].first;
      ee[v1^1].emplace_back(w1,v1);    //从i的入边点向i的出边点连边 w1
      if(j<e[i].size()-1){
        ee[v1].emplace_back(w2-w1,v2), //从i的小出边点向i的大出边点连边 w2-w1
        ee[v2].emplace_back(0,v1);     //从i的大出边点向i的小出边点连边 0
      }
    }
  }
  for(auto [w,v]:e[1]) ee[s].emplace_back(w,v);   //从s向1的出边点连边 w
  for(auto [w,v]:e[n]) ee[v^1].emplace_back(w,t); //从n的入边点向t连边 w
  
  dijkstra(s);
  cout<<d[t];
}

#include <bits/stdc++.h>
using namespace std;

namespace Sweet {

template <typename T> inline void read(T &x) {
    char ch;
    int f = 1;
    while (ch = getchar(), ch > '9' || ch < '0')
        if (ch == '-') f = -1;
    x = (ch ^ 48);
    while (ch = getchar(), ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48);
    x *= f;
}
template <typename T> inline void write(T x) {
    static int stk[100], top = 0;
    if (x == 0) return (void)putchar('0');
    if (x < 0) x = -x, putchar('-');
    while (x) stk[++top] = x % 10, x /= 10;
    while (top) putchar(stk[top--] + '0');
}

typedef long long ll;
const int N = 1e5 + 10, V = 4e5 + 10;

basic_string<pair<int, int> > e[V];
inline void add(int x, int y, int z) { e[x] += {y, z}; } // +=相当于push_back

struct T {
    int x;
    ll dis;
    T(int X, ll Dis) : x(X), dis(Dis) {}
    bool operator<(const T &rhs) const { return dis > rhs.dis; }
};
extern int s, t;
ll dis[V];
ll Dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<T> q;
    q.emplace(s, dis[s] = 0);
    static T u(0, 0);
    while (!q.empty()) {
        u = q.top(), q.pop();
        if (u.dis != dis[u.x]) continue;
        for (auto v : e[u.x]) {
            if (dis[v.first] > u.dis + v.second) {
                q.emplace(v.first, dis[v.first] = u.dis + v.second);
            }
        }
    }
    return dis[t];
}

struct Edge {
    int v, w, id;
    bool operator<(const Edge &rhs) const { return w < rhs.w; }
};
basic_string<Edge> g[N]; // 似乎比vector要快一点？
basic_string<Edge>::iterator it;

int n, m, s = 0, t = 1;
inline void main() {
    read(n), read(m);
    for (int i = 1, a, b, c; i <= m; ++i) {
        read(a), read(b), read(c);
        g[a] += {b, c, i << 1}, g[b] += {a, c, i << 1 | 1}; // 编号方式：异或1得到反向边
    }
    for (int i = 1; i <= n; ++i) {
        if (g[i].empty()) continue; // 后面迭代器的写法要求不能为空，直接用下标遍历不用判
        sort(g[i].begin(), g[i].end());
        for (auto j : g[i]) {
            add(j.id ^ 1, j.id, j.w);
            (i == 1) && (add(s, j.id, j.w), 0); // 短路表达式 = if
            (j.v == n) && (add(j.id, t, j.w), 0);
        }
        for (it = g[i].begin(), ++it; it != g[i].end(); ++it) {
            add(it->id, (it - 1)->id, 0);
            add((it - 1)->id, it->id, it->w - (it - 1)->w);
        }
    }
    write(Dijkstra());
}

}    // namespace Sweet

int main() {
    Sweet::main();
    return 0;
}