最短路
floyd
#include <iostream>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int n, m;
int dis[MAXN][MAXN];
int Min(int x, int y) {return x < y ? x : y;}
int Max(int x, int y) {return x > y ? x : y;}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
dis[i][j] = INF;
dis[i][i] = 0;
}
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
dis[u][v] = val;
dis[v][u] = val;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = Min(dis[i][k] + dis[k][j], dis[i][j]);
int s, t;
cin >> s >> t;
cout << dis[s][t];
return 0;
}
dijkstra
1.普通写法
#include <iostream>
using namespace std;
const int MAXN = 2505;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int dis[MAXN];
int w[MAXN][MAXN];
bool vis[MAXN];
int Min(int x, int y) {return x < y ? x : y;}
void dijkstra();
int main () {
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i++) {
dis[i] = INF;
for (int j = 1; j <= n; j++)
w[i][j] = INF;
}
dis[s] = 0;
for (int i = 1; i <= m; i++) {
int l, r, val;
cin >> l >> r >> val;
w[l][r] = val, w[r][l] = val;
}
dijkstra();
cout << dis[t];
return 0;
}
void dijkstra() {
for (int i = 1; i <= n; i++) {
if(vis[t] == 1) break;
int _min = INF, index;
for (int j = 1; j <= n; j++) {
if (vis[j] == 0 && dis[j] < _min) {
_min = dis[j];
index = j;
}
}
vis[index] = 1;
for (int j = 1; j <= n; j++) {
if (vis[j] == 0) {
dis[j] = Min(dis[j], dis[index] + w[index][j]);
}
}
}
}
2.优化
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 2005;
const int INF = 0x3f3f3f3f;
int n, m;
int dis[MAXN];
bool vis[MAXN];
struct node {
int v, val;
node () {}
node (int V, int Val) {
v = V, val = Val;
}
};
struct edge {
int now, val;
edge () {}
edge (int N, int V) {
now = N, val = V;
}
};
bool operator < (const edge x, const edge y) {
return x.val > y.val;
}
vector<node> g[MAXN];
bool dijkstra(int, int);
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
g[u].push_back (node (v, val));
g[v].push_back (node (u, val));
}
int s, t;
if (dijkstra (s, t)) cout << "-1";
else cout << dis[n];
return 0;
}
bool dijkstra (int s, int t) {
for (int i = 1; i <= n; i++) dis[i] = INF;
dis[s] = 0;
priority_queue<edge> p;
p.push( edge(s, 0));
while(!p.empty()) {
edge tem = p.top (); p.pop ();
int u = tem.now;
if (vis[u] == 1) continue;
vis[u] = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v, w = g[u][i].val;
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
p.push ( edge(v, dis[v]));
}
}
}
if(dis[t] == INF) return 1;
else return 0;
}
spfa
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
int dis[MAXN];
bool vis[MAXN];
struct node {
int v, val;
node () {}
node (int V, int VAL) {
v = V, val = VAL;
}
};
vector <node> g[MAXN];
int spfa (int, int);
int main () {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
g[u].push_back ( node (v, val));
}
int ans = spfa (1, n);
if (ans == INF) cout << "impossible";
else cout << ans;
return 0;
}
int spfa (int S, int T) {
for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0; dis[S] = 0;
queue <int> q; q.push (S);
while (!q.empty ()) {
int u = q.front (), size = g[u].size (); q.pop ();
vis[u] = 0;
for (int i = 0; i < size; i++) {
int v = g[u][i].v, w = g[u][i].val;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] +w;
if (vis[v] == 0) {
vis[v] = 1;
q.push (v);
}
}
}
}
return dis[T];
}
Processed:
0.013, SQL:
8
