KANO07 @ 2023-11-16 16:08:59
#include<bits/stdc++.h>
using namespace std;
int n;
int start;
//邻节点
struct adjNode{
int index;
int val;//此处val是边长
adjNode *next;
};
//头结点
struct headNode{
int val;
adjNode* first;
};
//图
struct Gragh{
headNode head[int(1e4+1)];
};
//连接边
void insertedge(Gragh &G,int i,int j,int value){
adjNode *tmp;
tmp = new adjNode;
tmp->index = j;
tmp->val = value;
tmp->next = G.head[i].first;
G.head[i].first = tmp;
}
//构造邻接表
void creat(Gragh &G){
int m;
cin>>n>>m>>start;
//初始化头结点
for(int i = 1;i<=n;i++){
G.head[i].val = i;
G.head[i].first = nullptr;
}
for(int i = 1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
insertedge(G,u,v,w);
}
}
//优先队列节点
struct minNode{
long long v;
long long index;
bool operator< (const minNode &t)const
{
return t.v<v;
}
};
vector<long long>dij(Gragh& G,int root){
priority_queue<minNode>que;
//distance[i]原点到i的距离
vector<long long>dis(n+1,INT_MAX);
dis[root] = 0;
que.push({0,root});
while(!que.empty())
{
minNode cur = que.top();
que.pop();
if(dis[cur.index]<cur.v) continue;
//更新相邻点
adjNode* i = G.head[cur.index].first;
while(i!=nullptr){
if(dis[i->index] > dis[cur.index]+i->val){
dis[i->index] = dis[cur.index]+i->val;
que.push({dis[i->index],i->index});
}
i=i->next;
}
}
return dis;
}
int main(){
Gragh G;
creat(G);
vector<long long>ans = dij(G,start);
//遍历输出
for(long long i = 1;i<=n;i++){
cout<<ans[i]<<" ";
}
return 0;
}
by Bodhi @ 2023-11-16 16:14:21
headNode数组开小了吧,数据范围给的是n<=1e5
by KANO07 @ 2023-11-16 17:24:57
@Bodhi 感谢感谢orz