记录一下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");
else
graph.print();
}
return 0;
}