请问大佬这个是不能用邻接矩阵存,还是怎么了,我这个为什么全错
查看原帖
请问大佬这个是不能用邻接矩阵存,还是怎么了,我这个为什么全错
701378
xbzzz楼主2022/4/16 13:13

请问大佬这个是不能用邻接矩阵存,还是怎么了,我这个为什么全错

#include<bits/stdc++.h>
using namespace std;
#define INF 99999999 //8个9 

vector<int> Dijkstra(vector<vector<int>> graph,int start){
	int n=graph.size(); //图中存储顶点的个数 
	vector<int> visit(n,0);
	vector<int> dist(n,0);
	for(int i=0;i<n;i++){
		dist[i]=graph[start][i]; //将dist[]初始化为最初图中路径长度
	}
	visit[start]=1; //起始顶点,传入的参数 
	//更新dist 
	for(int i=0;i<n;i++){
		int min_dist=INF;
		int middle=0;
		//找min_dist和middle 
		for(int j=0;j<n;j++){
			if(visit[j]==0 && min_dist>dist[j]){
				min_dist=dist[j];
				middle=j;
			}
		} 
		//以middle为中间节点 
		for(int j=0;j<n;j++){
			if(visit[j]==0 && dist[j]>dist[middle]+graph[middle][j]) {
				dist[j]=dist[middle]+graph[middle][j];
			}
		}
		visit[middle]=1;
	} 
	return dist;
}



int main(){
	int n,m,k; //n个节点,m条路,k为源点 
	cin>>n>>m>>k;
	k-=1;
	//初始化graph 
	vector<vector<int>> graph;
	for(int i=0;i<n;i++){
		graph.push_back(vector<int>());
		for(int j=0;j<n;j++){
			graph[i].push_back(INF);
		}
		graph[i][i]=0;
	}
	//传入graph的值 
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		x-=1;y-=1;
		graph[x][y]=z;
	} 
	//调用Dijkstra函数 
	vector<int> dist=Dijkstra(graph,k);
	for(int i=0;i<n;i++){
		cout<<dist[i];
		if(i!=n-1) cout<<" ";
	}
	return 0;
} 
2022/4/16 13:13
加载中...