1CR_wait_ME @ 2023-03-10 17:42:50
#include <iostream>
#define MAXNUM 1000000001
using namespace std;
int n, m;
int s;//起点
int graph[100001][100001];
int distance_[100001];
int SV[100001];
int S[100001];
int SVsize;
void Dij(){
//初始化
for(int i = 1; i<=n; i++){
distance_[i] = MAXNUM;
}
distance_[s] = 0;
SV[s] = 1;
SVsize++;
//算法部分
int newnode;
int minl;
while(1){
//拓展S集
if(!SVsize) return;
minl = MAXNUM;
for(int i = 1; i<=n; i++){
if(SV[i]){
if(distance_[i]<minl){
newnode = i;
minl = distance_[i];
}
}
}
S[newnode] = 1;
SV[newnode] = 0;
SVsize--;
//更新标签
for(int i = 1; i<=n; i++){
if(graph[newnode][i]&&!S[i]&&distance_[newnode]+graph[newnode][i]<distance_[i]){
if(distance_[i]==MAXNUM){
SV[i] = 1;
SVsize++;
}
distance_[i] = distance_[newnode]+graph[newnode][i];
}
}
}
return;
}
int main(){
cin >> n >> m >> s;
int u, v, w;
for(int i = 1; i<=m; i++){
cin >> u >> v >> w;
graph[u][v] = w;
}
Dij();
for(int i = 1; i<=n; i++){
cout << distance_[i] << " ";
}
return 0;
}
在本地测,提示源文件未编译,交上去就ME了 人快气炸了,哪位lalao帮忙看看 谢谢
by w9095 @ 2023-03-10 17:58:04
@running_icd 数组太大了,请换更好的存图方式。
by 1CR_wait_ME @ 2023-03-10 18:01:18
@w9095 所以,用……链式前向星?
by w9095 @ 2023-03-10 18:03:22
@running_icd 没错,这里 的链式前向星
by 1CR_wait_ME @ 2023-03-23 20:45:21
@w9095 谢谢!