会python真的可以为所欲为0(回)
353天前
这里还有人吗1(回)
538天前这里还有人吗0(回)
538天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
763天前到处都是羊，不想上班0(回)
843天前
鸽子
0(回)
847天前#include<iostream> |
#include<string> |
#include<cstdio> |
using namespace std; |
#define INF 0x7f7f7f7f |
const int N = 1005; //点的个数上限 |
int maze[N][N]; |
int dis[N]; |
bool vis[N]; |
//点的个数和边的条数 |
int n, m, S, T, K; |
void init() |
{ |
memset(maze, INF, sizeof(maze)); |
memset(dis, INF, sizeof(dis)); |
memset(vis, false, sizeof(vis)); |
} |
void dijkstra(int st) |
{ |
dis[st] = 0; |
for (int i = 1; i <= n; i++) |
{ |
//找到和起点距离最短的点 |
int minx = INF; |
int minmark; |
for (int j = 1; j <= n; j++) |
{ |
if (vis[j] == false && dis[j] <= minx) |
{ |
minx = dis[j]; |
minmark = j; |
} |
} |
//并标记 |
vis[minmark] = true; |
cout << minmark << endl; |
//更新所有和它连接的点的距离 |
for (int j = 1; j <= n; j++) |
{ |
if (vis[j] == false && dis[j] > dis[minmark] + maze[minmark][j]) |
dis[j] = dis[minmark] + maze[minmark][j]; |
} |
} |
} |
int main() |
{ |
cin >> n >> m >> S >> T >> K; |
init(); |
for (int i = 1; i <= m; i++) |
{ |
int x, y, len; |
scanf("%d %d %d", &x, &y, &len); |
if (x != y && maze[x][y] > len) |
{ |
maze[y][x] = len; |
maze[x][y] = len; |
} |
} |
//以S为起点跑一次dij |
dijkstra(S); |
//输出到T的距离 |
printf("%d\n", dis[T]); |
return 0; |
} |
