贺州学院Wenhf


私信TA

用户名:I7I08I9047

访问量:3452

签 名:

有没有大佬教我splay,在线等.gif

排  名 4
经  验 10946
参赛次数 10
文章发表 106
年  龄 0
在职情况
学  校 贺州学院
专  业

  自我简介:

wahfkgazjkhgAJKSghj

解题思路:

        1.jpg讲不出来,卖个萌。 实质也是贪心。


参考代码:

#include<bits/stdc++.h>
#define Inf 0xFFFFFF
using namespace std;
const int mapSize = 51;

int  Map[mapSize][mapSize];
int  dis[mapSize];
bool Vis[mapSize];
int  point, start;

void Dijkstra() {
	Vis[start] = true;
	for (int i = 0; i < point; i++) {
		dis[i] = Map[start][i] != 0 ? Map[start][i] : Inf;
	} dis[start] = 0;

	for (int poi = 1; poi < point; poi++) {
		int min = Inf, index;

		for (int i = 0; i < point; i++)
			if (!Vis[i] && dis[i] < min) {
				min = dis[i]; index = i;
			}
			
		Vis[index] = true;
		
		for (int i = 0; i < point; i++)
			if (!Vis[i] && Map[index][i] != 0 && dis[i] > dis[index] + Map[index][i])
				dis[i] = dis[index] + Map[index][i];
	}
}

int main() {
	cin >> point >> start;
	for (int i1 = 0; i1 < point; i1++)
		for (int i2 = 0; i2 < point; i2++)
			cin >> Map[i1][i2];

	Dijkstra();
	for (int i = 0; i < point; i++) {
		if(i != start)
			dis[i] < Inf ? cout << dis[i] << ' ' : cout << -1 << ' ';
	}
	cout << endl;
}


  评论区