记录一下Dijkstra的模板，主要加了一个优先队列，时间复杂度变成O(mlogn)，速度快了很多。
struct Edge
{int from, to, dist;Edge(int u, int v, int w) :from(u), to(v), dist(w) {}
};
struct HeapNode
{int d, u;HeapNode(int x, int y) :d(x), u(y) {}bool operator<(const HeapNode &rhs) const{return d > rhs.d;}
};
struct Dijkstra
{vector<Edge> edges; //边保存vector<int> G[maxn]; //保存每个点能到达的所有边bool done[maxn]; //是否已经永久标记int d[maxn]; //起点到各个点的距离int p[maxn]; //最短路的上一条弧void init(){for (int i = 0; i < maxn; i++)G[i].clear();edges.clear();}void addedge(int from, int to, int dist){edges.push_back(Edge(from, to, dist));G[from].push_back(edges.size());}void dij(){priority_queue<HeapNode> Q;for (int i = 0; i < n; i++) d[i] = INF;d[s] = 0;memset(done, 0, sizeof(done));Q.push(HeapNode(0,s));while (!Q.empty()){HeapNode x = Q.top(); Q.pop();int u = x.u;if (done[u]) continue;done[u] = true;for (int i = 0; i < G[u].size(); i++){Edge& e = edges[G[u][i]];if (d[e.to] > d[u] + e.dist){d[e.to] = d[u] + e.dist;p[e.to] = G[u][i];Q.push(HeapNode(d[e.to], e.to));}}}}
};
下面写一下cf上这道题：
题意：
给出一个无向图，现在要求将所有边权为0的边的权值变成大于等于1的值，问怎么变化使最后的最短路径和为l
要点：
基本就是一个最短路径，题目想起来不难，先把所有权值不为0的图进行一次dij，特判一下。然后将权值为0的边一条一条赋值为1放入图并进行dij，如果此时的最短路径d<=l，那就把这条边改成l - dij()+w即可，剩余所有边改成无穷大。但这题我WA了快10次，主要是输出很烦，而且一开始模板还写错，数组上限也开小了，还是太菜了。
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int maxm = 20010;//注意这里
const ll INF = 1000000000000000000;
int n, m, l, s, t, cnt,tot;
int S[maxm], T[maxm];struct Edge
{int from, to, dist;Edge(int u, int v, int w) :from(u), to(v), dist(w) {}
};
struct HeapNode
{int d, u;HeapNode(int x, int y) :d(x), u(y) {}bool operator<(const HeapNode &rhs) const{return d > rhs.d;}
};
struct Dijkstra
{vector<Edge> edges; //边保存vector<int> G[maxn]; //保存每个点能到达的所有边bool done[maxn]; //是否已经永久标记ll d[maxn]; //起点到各个点的距离int p[maxn]; //最短路的上一条弧void init(){for (int i = 0; i < maxn; i++)G[i].clear();edges.clear();}void addedge(int from, int to, int dist){edges.push_back(Edge(from, to, dist));G[from].push_back(edges.size() - 1);}ll dij(){priority_queue<HeapNode> Q;for (int i = 0; i < maxn; i++) d[i] = INF;d[s] = 0;memset(done, 0, sizeof(done));Q.push(HeapNode(0, s));while (!Q.empty()){HeapNode x = Q.top(); Q.pop();int u = x.u;if (done[u]) continue;done[u] = true;for (int i = 0; i < G[u].size(); i++){Edge& e = edges[G[u][i]];if (d[e.to] > d[u] + e.dist&&d[u]+e.dist<=l)//这里有个优化{d[e.to] = d[u] + e.dist;p[e.to] = G[u][i];Q.push(HeapNode(d[e.to], e.to));}}}return d[t];}void print(){printf("YES\n");int t = edges.size();for (int i = 0; i < t - 2; i += 2)printf("%d %d %d\n", edges[i].from, edges[i].to, edges[i].dist);//printf("------------\n");printf("%d %d %d\n", edges[t - 2].from, edges[t - 2].to, l - dij() + edges[t - 2].dist);//printf("------------\n");for (int i = tot; i<=cnt; i++)printf("%d %d %I64d\n", S[i], T[i], INF);}
};
Dijkstra graph;int main()
{//while (1){scanf("%d%d%d%d%d", &n, &m, &l, &s, &t);int u, v, w;graph.init();for (int i = 0; i < m; i++){scanf("%d%d%d", &u, &v, &w);if (w){graph.addedge(u, v, w);graph.addedge(v, u, w);}else{S[++cnt] = u;T[cnt] = v;}}tot = 1;if (graph.dij() < l)//一开始特判{//printf("%d\n", graph.dij());printf("NO\n");return 0;}else if (graph.dij() == l){graph.print();return 0;}for (; tot <= cnt; tot++)//将每个边分别赋值为1加入，如果最短路径小于l就脱出{graph.addedge(S[tot], T[tot], 1);graph.addedge(T[tot], S[tot], 1);if (graph.dij() <= l)break;}tot++;//printf("%d %d\n", tot, cnt);if (tot > cnt + 1)printf("NO\n");elsegraph.print();}return 0;
}