模版：
看了几个版本的dijkstra，最终以如下代码作为板子。
看如下代码之前，你需要先学这两位大佬的课程
https://www.bilibili.com/video/BV1Ya411L7gb/?spm_id_from=333.1387.collection.video_card.click&vd_source=34da0aa07edaca8b889ad016b25904d0
https://www.bilibili.com/video/BV14dXpYEEZS/?spm_id_from=333.337.search-card.all.click&vd_source=34da0aa07edaca8b889ad016b25904d0
前提： D=<V,E>且w_i>=0
优化：if(dis>d[u1]) continue;
合法性：
d[v1] = d[u1] + w1实时更新为更小值
↓pq.push({d[v1], v1})压入新的（更小的）距离
↓- 堆中关于
v1的条目：旧的（大）vs 新的（小）
↓ - 最小堆保证：小的先弹出，大的后弹出
↓ - 先弹出的：
dis == d[v1]（当前最小）→ 处理
后弹出的：dis > d[v1]（已过时） → 跳过
反证：假设弹出 (dis, u) 且 dis < d[u]
d[u]是当前已知最短距离dis < d[u]意味着存在更短路径- 但
Dijkstra性质：第一次弹出时d[u]已确定，不可能有更短的 - 矛盾！
模版：
struct edge{ll w,v;};
vector<edge> e[N];
ll starti,d[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;//w1<w2 void dijkstra(ll s){ll u1,v1,w1,dis;for(ll i=0;i<=n;++i) d[i]=INF;d[s]=0; pq.push({0,s});while(!pq.empty()){auto head=pq.top(); pq.pop(); dis=head.first; u1=head.second;if(dis>d[u1]) continue;//已经标记 直接出队 for(auto ed:e[u1]){v1=ed.v,w1=ed.w; if(d[u1]+w1<d[v1]){//核心:如果不能松弛 {w1,v1}不加入队列 d[v1]=d[u1]+w1;pq.push({d[v1],v1});} }}
}int main()
{for(ll i=1;i<=m;++i){cin>>a>>b>>c;e[a].push_back({c,b});}dijkstra(starti);return 0;
}