不会SPFA的同学们看过来
既然dalao们都在打SPFA，我也不会SPFA，所以写个Dijkstra的题解。
首先提醒那些和我一样感觉自己的代码对，刚从P3371 【模板】单源最短路径（弱化版）过来的同学。
这个题的边是无向图！！！
听到大佬说是模板题，我就从P3371直接过来交上了，然后WA掉9个点，，，我改了好长时间，，，才发现QAQ
还有很多大佬告诉我这是一道练SPFA的好题，的确，数据说得过，似乎也没人卡QAQ，但是我觉得那Dijkstra会更方便一些。
其实真的就是道模板题
我在这里细讲一下Dijkstra做法（包括堆优化方法）
1.Dijkstra无优化版
实际上Dijkstra的思想和Floyd的部分思想是一样的，有用到了一个神奇的东西：松弛操作
if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j];
QAQ？？？完了？？？
完了。这就是Dijkstra与Floyd的核心思想，Dijkstra就是把时间复杂度降低，范围缩小而已。
（相信都学过Dijkstra）
想必大家也都知道有一个操作，就是寻找最近的点，我们在写的时候是O(n)的。。。
不觉得太慢了吗？？？
于是我们有了~~~~
2.Dijkstra + 堆优化
不要觉得堆优化十分高大上，实际上只优化了一些最简单而又最费时间的操作。
大家还记得优先队列吗？？？（堆也行）
#include<queue> priority_queue<int> que;
就是这个东西，可以O(logn)的找到最近的点了QAQ
具体操作看代码吧！QAQ
代码
链式前向星存图(无优化的找不到了，这个只有带堆优化的QAQ，想看无优化的向下翻)：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define rep(i, x) for (int i = h[x]; i; i = e[i].nxt)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define ld long double
#define fi first
#define se second
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-');x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
struct edge{
int v, nxt, w;
} e[mn<<1];
int h[mn],p;
inline void add(int a,int b,int c){
p++;
e[p].nxt = h[a];
h[a] = p;
e[p].v = b;
e[p].w = c;
}
struct node{
int u,v;
bool operator <(const node &b) const{
return u > b.u;
}
};
/*
bool operator <(const node &a,const node &b) {
return a.u > b.u;
};
*/
int n, m, s, t;
int dis[mn];
priority_queue<node> q;
inline void Dij(int s){
go(i, 0, n, 1)
dis[i] = inf;
dis[s] = 0;
node o;
o.u = 0;
o.v = s;
q.push(o);
while (q.size()){
int u = q.top().v;
int d = q.top().u;
q.pop();
if(d!=dis[u])
continue;
rep(i,u){
int v = e[i].v;
int w = e[i].w;
if (dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
node p;
p.u = dis[v], p.v = v;
q.push(p);
}
}
}
}
int main(){
n=read(),m=read(),s=read(),t=read();
go(i,1,m,1){
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
}
Dij(s);
cout << dis[t];
cout << "\n";
return 0;
} vector暴力存图法（和链式前向星没啥区别，这个包括无优化和有优化的）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define go(i,j,n,k) for(register int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(register int i=j;i>=n;i-=k)
#define mn 110
#define inf 1<<30
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int kN = 100000+10;
const int INF = 2147483647;
int s, n, m, k;
int d[kN];
vector<pair<int, int> > G[kN];
bool vis[kN];
void dijkstra_naive(int s) {
for (int i = 0; i <= n; i++) d[i] = INF;
d[s] = 0;
for (int i = 1; i <= n; i++) {
// find min u, s.t. d[u] < d[i] for all i that vis[i] = false
int u = -1;
for (int j = 1; j <= n; j++) if (!vis[j]) {
if (u == -1 || d[j] < d[u]) {
u = j;
}
}
if (u == -1 || d[u] >= INF) break;
vis[u] = true;
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].first;
int w = G[u][j].second;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
}
}
}
}
void dijkstra(int s) {
for (int i = 0; i <= n; i++) d[i] = INF;
d[s] = 0;
priority_queue<pair<int, int> > q;
q.push(make_pair(0, s));
while (q.size()) {
int u = q.top().second;
q.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].first;
int w = G[u][i].second;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push(make_pair(-d[v], v));
}
}
}
}
int main() {
n = read();
m = read();
s = read();
t = read();
go(i,1,m,1){
int u=read(), v=read(), w=read();
pair<int, int> p;
p.first = v;
p.second = w;
G[u].push_back(p) ;
p.first = u;
p.second = w;
G[v].push_back(p) ;
}
dijkstra_naive(s);
//dijkstra(s);
cout << d[t];
} 如果有同学想要板子之类的东西，可以看我的博客QAQ，有部分模板代码QAQ
京公网安备 11010502036488号