首尾TLE，64分求条（悬关）

Ybw0731 @ 2024-10-17 21:42:21

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
priority_queue<int>que;
struct node{
    int vv,ww;
};
struct edge{
    int w,to,nxt;
}e[N];
int n,m,st,dis[N],cnt,head[N];
bool vis[N];
void add(int u,int v,int d){
    cnt++;
    e[cnt].w=d;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dijkstra(int st){
    que.push({st});
    vis[st]=1;
    dis[st]=0;
    while(!que.empty()){
        int u=que.top();
        que.pop(); 
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w; 
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                vis[v]=1;
                que.push({v});
            }
        }
    }
}
int main(){
    cin>>n>>m>>st;
    for(int i=1;i<=n;i++)dis[i]=INF;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(st);
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
    return 0;
}

by xunhuanyihao @ 2024-10-17 21:46:35

que.pop();
if (!vis[u]) continue;
vis[u]=1;

后面的 vis[v] = 1 删掉

by Ybw0731 @ 2024-10-17 21:57:51

@xunhuanyihao,这样改样例都过不了。

by Chtholly__Nota @ 2024-10-17 22:08:15

额，可能是想用堆优化，但是放入堆的是节点标号，并不是权值，所以没有优化效果。。

by Ybw0731 @ 2024-10-17 22:16:22

@Chtholly__Nota,那你帮我想个办法，怎么改呢？

by Ybw0731 @ 2024-10-17 22:19:05

@Chtholly__Nota,我用我没加优化的代码提交了，变成了全T

by Chtholly__Nota @ 2024-10-17 22:22:15

emmmm，想想

by Chtholly__Nota @ 2024-10-17 22:38:22

额，过了，你看看(链式前向星不大熟，调的有点久

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
priority_queue<pair<int,int> >que;
struct node{
    int vv,ww;
};
struct edge{
    int w,to,nxt;
}e[N];
int n,m,st,dis[N],cnt,head[N];
bool vis[N];
void add(int u,int v,int d){
    cnt++;
    e[cnt].w=d;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dijkstra(int st){
    que.push({-e[st].w,st});
    dis[st]=0;
    while(!que.empty()){
        pair<int,int> u=que.top();
        que.pop(); 
        if(vis[u.second]) continue;
        vis[u.second]=1;
        for(int i=head[u.second];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            if(dis[v]>dis[u.second]+w && vis[v]==0){
                dis[v]=dis[u.second]+w;
                que.push({-dis[v],v});
            }
        }
    }
}
int main(){
    cin>>n>>m>>st;
    for(int i=1;i<=n;i++) dis[i]=INF;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra(st);
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
    return 0;
}

by Huangjh1 @ 2024-10-20 19:20:57

dis数组只有第s位要初始化为0，其他的都要初始化为无穷大。同样可以在que.pop()后面判断一下vis[u]是否被访问过了。当然，其实还建议用小根堆优化一下，如果学过重载运算符的画可以自己改改试试看

by Ybw0731 @ 2024-10-21 20:04:55

已AC，此结帖