建的是有向边,数组也没有开小,求问各位大佬哪里写挂了
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
int dis[100005];
bool vis[100005];
struct edge{
int v,w;
};
vector<edge> rel[100005];
const int INF=0x3f3f3f3f;
void dijkstra();
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
rel[u].push_back({v,w});
}
memset(dis,0x3f,sizeof(dis));
dijkstra();
for(int i=1;i<=n;++i)
printf("%d ",dis[i]);
printf("\n");
return 0;
}
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
};
void dijkstra(){
priority_queue<int,vector<int>,cmp> q;
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int x=q.top();
q.pop();
for(int i=0;i<rel[x].size();++i){
int y=rel[x][i].v;
if(dis[x]+rel[x][i].w<dis[y]){
dis[y]=dis[x]+rel[x][i].w;
if(!vis[y]){
vis[y]=true;
q.push(y);
}
}
}
}
}