行动欲望π @ 2022-08-20 10:24:31
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dis[100010],book[100010];
vector <int > v[200010][10];
struct node{
int p,zhi;
};
bool operator <(node n1,node n2){
return n1.zhi >n2.zhi;
}
priority_queue<node> q;
signed main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v1,w;
cin>>u>>v1>>w;
v[u][1].push_back(v1);
v[u][2].push_back(w);
}
for(int i=1;i<=n;i++){
dis[i]=0x7ffffff;
}
dis[s]=0;
/*for(int j=0;j<v[s][1].size();j++){
int yy=v[s][1][j];
dis[yy]=min(dis[yy],dis[s]+v[s][2][j]);q.push({yy,dis[yy]});
}*/q.push({s,0});
while(q.size()>0){
node n1=q.top();
q.pop();
int hhh=n1.p;
/*for(int j=1;j<=n;j++){
if(dis[j]!=0x7ffffff&&book[j]!=1){
jjj=min(dis[n],jjj);
if(jjj==dis[n]){
hhh=n;
}
}
}*/
if(book[hhh]==1) continue;
book[hhh]=1;
for(int j=0;j<v[hhh][1].size();j++){
int hh=v[hhh][1][j];
dis[hh]=min(dis[hh],dis[hhh]+v[hhh][2][j]);
q.push({hh,dis[hh]});
}
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<' ';
}
return 0;
}
by 行动欲望π @ 2022-08-20 10:25:46
第5个测试点没过…… _
_
by Fish9块1 @ 2022-08-20 10:32:17
@行动欲望π 单向边。
by 行动欲望π @ 2022-08-20 10:51:00
谢谢,我已经找到错了万分感谢……@Fish9块1