84pts TLE求调

_lxc__ @ 2024-12-14 18:42:24

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
int n,m,s,dis[N],vis[N];
struct node{
    int v,w;
};
struct Node{
    int val,id;
};
vector<node> adj[N];
bool operator <(const Node &x,const Node &y){
    return x.val>y.val;
}
void solve(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<Node> pq;
    pq.push({0,s});
    while(pq.size()){
        Node t=pq.top();
        pq.pop();
        int u=t.id;
        vis[u]=1;
        for(auto x:adj[u]){
            int v=x.v,w=x.w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    pq.push({dis[v],v});
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(register int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back({v,w});
    }
    solve(s);
    for(register int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by sh_Andy @ 2024-12-14 19:01:06

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
int n,m,s,dis[N],vis[N];
struct node{
    int v,w;
};
struct Node{
    int val,id;
};
vector<node> adj[N];
bool operator <(const Node &x,const Node &y){
    return x.val>y.val;
}
void solve(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<Node> pq;
    pq.push({0,s});
    while(pq.size()){
        Node t=pq.top();
        pq.pop();
        int u=t.id;
    if(vis[u]) continue;   //<---这里
    vis[u]=1;
        for(auto x:adj[u]){
            int v=x.v,w=x.w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    pq.push({dis[v],v});
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(register int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back({v,w});
    }
    solve(s);
    for(register int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by sh_Andy @ 2024-12-14 19:03:05

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+10;
int n,m,s,dis[N],vis[N];
struct node{
    int v,w;
};
struct Node{
    int val,id;
};
vector<node> adj[N];
bool operator <(const Node &x,const Node &y){
    return x.val>y.val;
}
void solve(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<Node> pq;
    pq.push({0,s});
    while(pq.size()){
        Node t=pq.top();
        pq.pop();
        int u=t.id;
    if(vis[u]) continue;   //<---这里
    vis[u]=1;
        for(auto x:adj[u]){
            int v=x.v,w=x.w;
            if(!vis[v]&&dis[u]+w<dis[v]){   //<---这里
               dis[v]=dis[u]+w;
                    pq.push({dis[v],v});
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(register int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back({v,w});
    }
    solve(s);
    for(register int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by _lxc__ @ 2024-12-14 20:35:25

@sh_Andy thk