#include <bits/stdc++.h>
#define pb push_back
#define _for(i,a,b) for(int i = (a);i < (b);i ++)
#define INF 0x3f3f3f3f
using namespace std;
const int maxn =
50003;
struct edge
{
int to;
int cost;
};
vector<edge>
G[maxn];
//G[s].push_back(t);from s to t,directed
int V,E;
//from s to other V
void shortest_path(
int s)
{
}
int main()
{
scanf("%d %d",&V,&
E);
_for(i,0,E)
{
int s,t,c;
scanf("%d %d %d",&s,&t,&
c);
G[s].push_back(edge{t,c});
G[t].push_back(edge{s,c});
}
shortest_path(0);
cout << d[
6] <<
endl;
}
/*
10
1 2
2 5
2 4
3 6
3 2
4 10
5 1
5 3
6 5
6 9
*/
main函数
//from s to other V
int d[maxn];
void shortest_path(
int s)
{
_for(i,0,V)
d[i] =
INF;
d[s] =
0;
while(
1)
{
bool update =
false;
_for(i,0,V)
{
_for(j,0,G[i].size())
{
edge e =
G[i][j];
if(d[i] != INF && d[e.to] > d[i] +
e.cost)
{
d[e.to] = d[i] +
e.cost;
update =
true;
}
}
}
if(!update)
break;
}
}
Bellman-Ford
//from s to other V
bool used[maxn];
int d[maxn];
void shortest_path(
int s)
{
_for(i,0,V)
{
d[i] =
INF;
used[i] =
false;
}
d[s] =
0;
while(
1)
{
int v = -
1;
_for(i,0,V)
if(!used[i] && (v==-
1 || d[i] < d[v])) v =
i;
if(v==-
1)
break;
used[v] =
true;
_for(i,0,G[v].size())
d[G[v][i].to] = min(d[G[v][i].to],d[v]+
G[v][i].cost);
}
}
Dijkstra
//from s to other V
typedef pair<
int,
int> P;
//first 是最短距离，second 是顶点编号
int d[maxn];
void shortest_path(
int s)
{
priority_queue<P,vector<P>,greater<P>>
que;
_for(i,0,V)
d[i] =
INF;
d[s] =
0;
que.push(P{0,s});
while(!
que.empty())
{
P p =
que.top();que.pop();
int v =
p.second;
if(d[v] < p.first)
continue;
_for(i,0,G[v].size())
{
edge e =
G[v][i];
if(d[e.to] > d[v] +
e.cost)
{
d[e.to] = d[v] +
e.cost;
que.push(P{d[e.to],e.to});
}
}
}
}
Dijkstra(priority_queue)
//from s to other V
typedef pair<
int,
int> P;
//first 是最短距离，second 是顶点编号
int d[maxn];
int pre[maxn];
void shortest_path(
int s)
{
priority_queue<P,vector<P>,greater<P>>
que;
_for(i,0,V)
d[i] =
INF;
_for(i,0,V)
pre[i] = -
1;
d[s] =
0;
que.push(P{0,s});
while(!
que.empty())
{
P p =
que.top();que.pop();
int v =
p.second;
if(d[v] < p.first)
continue;
_for(i,0,G[v].size())
{
edge e =
G[v][i];
if(d[e.to] > d[v] +
e.cost)
{
d[e.to] = d[v] +
e.cost;
que.push(P{d[e.to],e.to});
pre[e.to] =
v;
}
}
}
}
//到终点t
vector<
int> get_path(
int t)
{
vector<
int>
p;
for(; t != -
1;t =
pre[t]) p.pb(t);
reverse(p.begin(),p.end());
return p;
}
Dijkstra(priority_queue)路径还原
bool find_negative_loop()
{
memset(d,0,
sizeof(d));
_for(i,0,V)
_for(j,0,V)
_for(k,0,G[j].size())
{
edge e =
G[j][k];
if(d[e.to] > d[j] +
e.cost)
{
d[e.to] = d[j] +
e.cost;
if(i==V-
1)
return true;
}
}
return false;
}
判断负圈
//from s to other V
int d[maxn][maxn];
void shortest_path()
{
memset(d,INF,sizeof(d));
_for(i,0,V)
_for(j,0,G[i].size())
{
edge e =
G[i][j];
d[i][e.to] =
e.cost;
}
_for(k,0,V)
_for(i,0,V)
_for(j,0,V)
d[i][j] = min(d[i][j],d[i][k]+
d[k][j]);
}
Floyd-Warshall
//from s to other V
//return false表示有负圈
int d[maxn];
// 距离数组
int vis[maxn];
// 判断点是否在队列里
int pre[maxn];
// 路径还原
int cnt[maxn];
// 进队列次数
bool shortest_path(
int s)
{
memset(d,INF,sizeof(d));
memset(vis,0,
sizeof(vis));
memset(cnt,0,
sizeof(cnt));
memset(pre,-
1,
sizeof(pre));
deque<
int>
q;
d[s] =
0,cnt[s] = vis[s] =
1;
q.push_back(s);
while(!
q.empty())
{
int now =
q.front();q.pop_front();
vis[now] =
0;
_for(i,0,G[now].size())
{
if(d[G[now][i].to] > d[now] +
G[now][i].cost)
{
d[G[now][i].to] = d[now] +
G[now][i].cost;
pre[G[now][i].to] =
now;
if(!
vis[G[now][i].to])
{
if(V == ++cnt[G[now][i].to])
return false;
if(!q.empty() && d[G[now][i].to] < d[q.front()])
//队列非空且优于队首（SLF）
q.push_front(G[now][i].to);
else q.push_back(G[now][i].to);
vis[G[now][i].to] =
1;
}
}
}
}
return 0;
}
//到终点t
vector<
int> get_path(
int t)
{
vector<
int>
p;
for(; t != -
1;t =
pre[t]) p.pb(t);
reverse(p.begin(),p.end());
return p;
}
SPFA(SLF优化，路径还原)
Bellman O(|V|*|E|)，可处理负边
Dijkstra 优先队列实现 O(|E|*log|V|)，不可处理负边
Floyd O(|V^3|) d[i][i]为负数时可判定有负圈
SPFA O(|V|*|E|)，如果返回false则有负圈
转载于:https://www.cnblogs.com/Asurudo/p/10566321.html
