社区讨论

dij样例都不过求助

P1342[CERC1998] 请柬参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo8uzm9l
此快照首次捕获于
2023/10/28 01:00
2 年前
此快照最后确认于
2023/10/28 01:00
2 年前
查看原帖
CPP
#include <iostream>
#include <queue>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

template<typename T=int>
inline void write(T X){
    if(X<0) putchar('-'),X=~(X-1);
    T s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}

const int N=2e6+5,M=2e6+5,inf=0x3f3f3f3f;
struct edge{
    int to,nxt,val;
}e[2][M];
int n,m,s,u,v,w;
int head[N],top;
int dist[N],vis[N];
long long ans;
priority_queue<pair<int,int>> q;

void add(int u,int v,int w,int id){
    top++;
    e[id][top].to=v;
    e[id][top].val=w;
    e[id][top].to=head[u];
    head[u]=top;
}

void dijkstra(int id){
    for(int i=1; i<=n; i++) dist[i]=inf,vis[i]=0;
    dist[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[id][i].nxt){
            v=e[id][i].to;
            if(dist[v]>dist[u]+e[id][i].val){
                dist[v]=dist[u]+e[id][i].val;
                q.push(make_pair(-dist[v],v));
            }
        }
    }
}

int main(){
    n=read(),m=read(),s=1;
    while(m--){
        u=read(),v=read(),w=read();
        add(u,v,w,0);
        add(v,u,w,1);
    }
    dijkstra(0);
    for(int i=1; i<=n; i++) ans+=dist[i];
    dijkstra(1);
    for(int i=1; i<=n; i++) ans+=dist[i];
    write(ans);
    return 0;
}
rt,样例输出 63666574026366657402

回复

4 条回复,欢迎继续交流。

正在加载回复...