记录一下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 edges; //边保存 vector 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 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#include #include #include #include #include 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 edges; //边保存 vector 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 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"); else graph.print(); } return 0;}