Alvin1204 @ 2024-08-06 10:07:36
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Edge{int next,to,dis;}e[200010];
int head[200010],cnt;
void addedge(int from,int to,int dis){
e[cnt].next=head[from];
e[cnt].to=to;
e[cnt].dis=dis;
head[from]=cnt++;
return ;
}
int n,m,s;
#define pi pair<int,int>
long long dis[100010];
int vis[100010];
void dijkstra(){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
priority_queue<pi,vector<pi>,greater<pi> > q;
dis[s]=0;vis[s]=1;//自己感觉这错了，但不知道怎么改
q.push(make_pair(0,s));
while(q.size()){
int x=q.top().second;
q.pop();
for(int i=head[x];~i;i=e[i].next){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].dis){
dis[y]=dis[x]+e[i].dis;
if(!vis[y])
q.push(make_pair(dis[y],y)),vis[y]=1;//自己感觉这错了，但不知道怎么改
}
}
}
return ;
}
int main(){
memset(head,-1,sizeof head);
scanf("%d%d%d",&n,&m,&s);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
}
dijkstra();
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
return 0;
} by ANDER_ @ 2024-08-06 10:11:20
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
//#define MSOD
const int N = 1e5 + 5, M = 5e5 + 5, INF = 0x7f7f7f7f;
int n, m, s, dis[N];
bool vis[N];
vector<pair<int, int>> edge[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
inline void solve() {
cin>>n>>m>>s;
for(int i = 1, a, b, c ; i <= m ; i ++) {
cin>>a>>b>>c;
edge[a].push_back({b, c});
}
memset(dis, INF, sizeof(dis));
dis[s] = 0;
que.push({dis[s], s});
while(!que.empty()) {
pair<int, int> tmp = que.top();
que.pop();
if(!vis[tmp.second]) {
vis[tmp.second] = true;
for(auto i : edge[tmp.second]) {
if(!vis[i.first] && dis[i.first] > tmp.first + i.second) {
dis[i.first] = tmp.first + i.second;
que.push({dis[i.first], i.first});
}
}
}
}
for(int i = 1 ; i <= n ; i ++) {
cout<<min(dis[i], 2147483647ll)<<" ";
}
return;
}
signed main() {
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
#ifdef MSOD
int T;
for(cin>>T ; T -- ; ) {
solve();
}
#else
solve();
#endif
return 0;
}粘下我的
by Ame_wiki @ 2024-08-06 10:19:54
捕捉野生 @Alexander_1
by wizard（偷开O2 @ 2024-08-06 10:19:56
@Alvin1204
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
priority_queue<pi,vector<pi>,greater<pi> > q;
dis[s]=0;//自己感觉这错了，但不知道怎么改
q.push(make_pair(0,s));
while(q.size()){
int x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];~i;i=e[i].next){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].dis){
dis[y]=dis[x]+e[i].dis;
q.push(make_pair(dis[y],y));//自己感觉这错了，但不知道怎么改
}
}
}每次判断优先队列中的元素时，你直接把这个元素判掉，就不用执行扫边操作了。
by wizard（偷开O2 @ 2024-08-06 10:22:17
@Alvin1204 你的确标对了你所有写炸了的地方。
by Alvin1204 @ 2024-08-06 10:41:58
谢谢@Alexander_1
by Alvin1204 @ 2024-08-06 10:43:01
谢谢@wizard（偷开O2
by hblhuangbolun @ 2024-08-07 18:17:32
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,s,cnt,dis[200100],vis[200100],head[200100];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{
int v,w,next;
}edge[200100];
void add(int u,int v,int w)
{
edge[++cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dijkstra()
{
memset(dis,127,sizeof(dis));
q.push(make_pair(0,s));
dis[s]=0;
vis[s]=1;
while(!q.empty())
{
int k,minn=0x7fffffff;
k=q.top().second,minn=q.top().first;
q.pop();
if(vis[k]==0 || k==s)
{
vis[k]=1;
for(int j=head[k]; j!=0; j=edge[j].next)
{
if(dis[edge[j].v] > dis[k]+edge[j].w)
{
dis[edge[j].v]=dis[k]+edge[j].w;
q.push(make_pair(dis[edge[j].v],edge[j].v));
}
}
}
}
}
void read()
{
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);
if(u!=v) add(u,v,w);
}
}
void print()
{
for(int i=1; i<=n; i++)
{
printf("%d ",dis[i]);
}
}
int main()
{
read();
dijkstra();
print();
}