求1-n最长边最小的路径。
最短路变形。dis值向后延申的方式是：$$dis[j]=min(dis[j],max(dis[i],w(i,j))$$
显然满足dijkstra贪心的选择方式。spfa也当然可以用。
写上三种方式，就当是模板好了。
spfa
复杂度：\(O(kE)/O(VE)\)
spfa的主要思想是不断松弛。注意spfa的更新策略，先更新\(dis\)值，再根据\(vis\)判断是否丢到\(queue\)中。
#include <bits/stdc++.h>
const int maxn = 100000;
const int maxm = 200000;
using namespace std;
int n, m;
int to[maxm * 2 + 10];
int w[maxm * 2 + 10];
int nex[maxm * 2 + 10];
int head[maxn + 10], cnt = 0;
void addEdge(int a, int b, int c)
{
to[cnt] = b; w[cnt] = c;
nex[cnt] = head[a]; head[a] = cnt++;
to[cnt] = a; w[cnt] = c;
nex[cnt] = head[b]; head[b] = cnt++;
}
int vis[maxn + 10];
int dis[maxn + 10];
void spfa()
{
queue<int> q;
dis[1] = 0;
q.push(1);
vis[1] = 1;
while (!q.empty())
{
int x = q.front(); q.pop();
vis[x] = 0;
// printf("current node: %d %d\n", x, dis[x]);
for (int i = head[x]; i != -1; i = nex[i])
{
int l = to[i];
if (max(dis[x], w[i]) < dis[l])
{
dis[l] = max(dis[x], w[i]);
if (!vis[l])
{
q.push(l);
vis[l] = 1;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
for (int i = 1, a, b, c; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c);
}
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
spfa();
printf("%d\n", dis[n]);
return 0;
}
dijkstra
会超时。
复杂度：\(O(V^2)\)
dijkstra的主要思想是一共\(V\)次贪心的选择当前未确定点中\(dis\)值最小的那一个确定。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
const int maxn = 100000;
const int maxm = 200000;
using namespace std;
int n, m;
int to[maxm * 2 + 10];
int w[maxm * 2 + 10];
int nex[maxm * 2 + 10];
int head[maxn + 10], cnt = 0;
void addEdge(int a, int b, int c)
{
to[cnt] = b; w[cnt] = c;
nex[cnt] = head[a]; head[a] = cnt++;
to[cnt] = a; w[cnt] = c;
nex[cnt] = head[b]; head[b] = cnt++;
}
int done[maxn + 10];
int dis[maxn + 10];
void dijkstra()
{
dis[1] = 0;
for (int i = 1; i <= n; i++)
{
int x = 0, mmin = inf;
for (int j = 1; j <= n; j++)
{
if (!done[j] && dis[j] < mmin)
mmin = dis[x = j];
}
done[x] = 1;
for (int j = head[x]; j != -1; j = nex[j])
{
int l = to[j];
dis[l] = min(dis[l], max(dis[x], w[j]));
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
for (int i = 1, a, b, c; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c);
}
memset(done, 0, sizeof(done));
memset(dis, 0x3f, sizeof(dis));
dijkstra();
printf("%d\n", dis[n]);
return 0;
}
heap_dijkstra
复杂度（stl优先队列实现，由于每条边最多被访问一次，堆中最多会有\(E\)个节点）：\(O(ElogE)\)，当图趋于完全图时，复杂度趋于\(O(V^2logV)\)，应当使用一般实现的dijkstra算法。
堆优化dijkstra，主要思想是利用堆加速每一次值最小（未确定）的点的选择。实际实现略有不同，所以复杂度并非\(O(VlogV)\)。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
const int maxn = 100000;
const int maxm = 200000;
using namespace std;
int n, m;
int to[maxm * 2 + 10];
int w[maxm * 2 + 10];
int nex[maxm * 2 + 10];
int head[maxn + 10], cnt = 0;
void addEdge(int a, int b, int c)
{
to[cnt] = b; w[cnt] = c;
nex[cnt] = head[a]; head[a] = cnt++;
to[cnt] = a; w[cnt] = c;
nex[cnt] = head[b]; head[b] = cnt++;
}
struct tNode
{
int d, u; // estimated dis, id of vertex
tNode(int dd, int uu): d(dd), u(uu){}
bool operator < (const tNode &y) const
{
return d > y.d;
}
};
int done[maxn + 10];
int dis[maxn + 10];
void heap_dijkstra()
{
priority_queue<tNode> q;
dis[1] = 0;
q.push(tNode(0, 1));
while (!q.empty())
{
tNode x = q.top(); q.pop();
int u = x.u;
if (done[u])
continue;
done[u] = 1;
for (int i = head[u]; i != -1; i = nex[i])
{
int l = to[i];
if (dis[l] > max(dis[u], w[i]))
{
dis[l] = max(dis[u], w[i]);
q.push(tNode(dis[l], l));
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
for (int i = 1, a, b, c; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c);
}
memset(done, 0, sizeof(done));
memset(dis, 0x3f, sizeof(dis));
heap_dijkstra();
printf("%d\n", dis[n]);
return 0;
}