为了回忆起以前的算法,写了一个最短路,看看就行
C++ 代码
#include<iostream>
#include<cstring>
#define INF 0x3f3f3f3f
#define m(a,b) memset(a,b,sizeof(a))
#define N 105
using namespace std;
int w[N][N], dis[N], vis[N];
int a, b, c, d;
int Dij() {
dis[a] = 0;
for (int i = 0; i < 100; i++) {
int t = -1;
for (int j = 0; j <=100; j++) {
if (!vis[j] && (t == -1 || dis[j] < dis[t]))
t = j;
}
vis[t] = 1;
for (int j = 0; j <= 100; j++)
dis[j] = min(dis[j], dis[t] + w[t][j]);
}
return dis[b];
}
int main() {
m(dis, INF);
cin >> a >> b;
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 100; j++) {
w[i][j] = w[j][i] = abs(i - j);
}
}
cin >> c >> d;
w[c][d] = w[d][c] = 0;
cout << Dij();
return 0;
}