用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

dijkstra算法计算从S到T的最短路径

2019-07-28 作者:Playboy_lh举报

[c++]代码库

#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;
	}



分享到:
更多

网友评论    (发表评论)


发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。