1 条题解
-
1
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define go(i, j, n, k) for (int i = j; i <= n; i += k) #define fo(i, j, n, k) for (int i = j; i >= n; i -= k) #define rep(i, x) for (int i = h[x]; i; i = e[i].nxt) #define mn 100010 #define mm 200020 #define inf 2147483647 #define ll long long #define ld long double #define fi first #define se second #define root 1, n, 1 #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define bson l, r, rt inline int read(){ int f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();} while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } inline void write(int x){ if (x < 0)putchar('-'),x = -x; if (x > 9)write(x / 10); putchar(x % 10 + '0'); } //This is AC head above... struct node{ int v, nxt, w; } e[mm << 1]; int h[mn], p; inline void add(int a,int b,int c){ e[++p].nxt = h[a]; h[a] = p; e[p].v = b; e[p].w = c; } int dis[mn]; int n, m, s, t; struct tree{ int minw, minv; }; struct SegmentTree{ tree z[mn << 2]; inline void update(int rt){ z[rt].minw = min(z[rt << 1].minw, z[rt << 1 | 1].minw);//维护区间最小值 z[rt].minv = (z[rt << 1].minw < z[rt << 1 | 1].minw) ? z[rt << 1].minv : z[rt << 1 | 1].minv;//维护区间最小值位置 } inline void build(int l,int r,int rt){//建树 if(l==r){ z[rt].minw = l == s ? 0 : inf;//我们可以直接建树时把s的点设置为0 z[rt].minv = l;//记录最小值位置,方便修改 return; } int m = (l + r) >> 1; build(lson); build(rson); update(rt); } inline void modify(int l,int r,int rt,int now,int v){//单点修改 if(l==r){ z[rt].minw = v; return; } int m = (l + r) >> 1; if(now<=m) modify(lson, now, v); else modify(rson, now, v); update(rt); } } tr; inline void Dij(){//Dijkstra的核心部分 go(i,1,n,1){ dis[i] = inf; }//初始化dis dis[s] = 0; while(tr.z[1].minw < inf){//这里就是判断是否为空 int x = tr.z[1].minv;//取整个线段树中最小的点 tr.modify(root, x, inf);//单点修改最小的点为inf rep(i,x){ int v = e[i].v; if(dis[v] > dis[x] + e[i].w){ dis[v] = dis[x] + e[i].w; tr.modify(root, v, dis[x] + e[i].w);//这里就是类似入队操作 } } } } int main(){ n = read(), m = read(), s = read(), t=read(); go(i,1,m,1){ int x = read(), y = read(), v = read(); add(x, y, v); add(y, x, v);//这个一定记住,无向图要正反两条边QAQ } tr.build(root);//建树 Dij();//Dijkstra cout << dis[t]; return 0; }
- 1
信息
- ID
- 340
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 4
- 已通过
- 4
- 上传者