为什么三个点TLE？？？HELP！！！

wdzxghl @ 2020-07-24 17:05:58

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010,inf=INT_MAX;
struct Edge {
    long long to,next,w;
} edge[maxn];
Edge edge1[maxn];
long long dis[maxn],p[maxn],vis[maxn],edge_num,edge_num1,dis1[maxn],p1[maxn],vis1[maxn];
int n,m;
void add_edge(int u,int v,int w) {
    edge[++edge_num].next=p[u];
    edge[edge_num].to=v;
    edge[edge_num].w=w;
    p[u]=edge_num;
}
void add_edge1(long long u,long long v,long long w) {
    edge1[++edge_num1].next=p1[u];
    edge1[edge_num1].to=v;
    edge1[edge_num1].w=w;
    p1[u]=edge_num1;
}

void dijkstra() {
    priority_queue<pair<long,long> >que;
    memset(vis,1,sizeof(vis));
    for(long long i=1; i<=n; i++)
        dis[i]=inf;

    dis[1]=0;
    vis[1]=0;

    que.push(make_pair(0,1));
    while(!que.empty()) {
        int x=que.top().second;
        que.pop();
        for(long long i=p[x]; i; i=edge[i].next) {
            long long tmp=edge[i].to;
            if(dis[tmp]>dis[x]+edge[i].w) {
                dis[tmp]=dis[x]+edge[i].w;
                que.push(make_pair(-dis[tmp],tmp));
            }
        }
    }
}
void dijkstra1() {
    priority_queue<pair<int,int> >que1;
    memset(vis1,1,sizeof(vis1));
    for(long long i=1; i<=n; i++)
        dis1[i]=inf;

    dis1[1]=0;
    vis1[1]=0;

    que1.push(make_pair(0,1));
    while(!que1.empty()) {
        long long x=que1.top().second;
        que1.pop();
        for(long long i=p1[x]; i; i=edge1[i].next) {
            long long tmp=edge1[i].to;
            if(dis1[tmp]>dis1[x]+edge1[i].w) {
                dis1[tmp]=dis1[x]+edge1[i].w;
                que1.push(make_pair(-dis1[tmp],tmp));
            }
        }
    }
}
int main() {
    cin>>n>>m;
    memset(p,0,sizeof(p));
    while(m--) {
        long long u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
        add_edge1(v,u,w);
    }
    dijkstra();
    dijkstra1();
    long long cnt=0;
    for(int i=1; i<=n; i++)
        cnt+=dis[i]+dis1[i];
    cout<<cnt<<endl;
    return 0;
}

by Eloik @ 2020-10-12 21:36:47

@wdzxghl 你没有判断当前点是否访问过，看注释就知道了

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010,inf=INT_MAX;
struct Edge {
    long long to,next,w;
} edge[maxn];
Edge edge1[maxn];
long long dis[maxn],p[maxn],vis[maxn],edge_num,edge_num1,dis1[maxn],p1[maxn],vis1[maxn];
int n,m;
void add_edge(int u,int v,int w) {
    edge[++edge_num].next=p[u];
    edge[edge_num].to=v;
    edge[edge_num].w=w;
    p[u]=edge_num;
}
void add_edge1(long long u,long long v,long long w) {
    edge1[++edge_num1].next=p1[u];
    edge1[edge_num1].to=v;
    edge1[edge_num1].w=w;
    p1[u]=edge_num1;
}

void dijkstra() {
    priority_queue<pair<long long,long long> >que;
    //vis初始化为0即可
    memset(vis,0,sizeof(vis));
    for(long long i=1; i<=n; i++)
        dis[i]=inf;

    dis[1]=0;

    //不必初始化vis[1]
    //vis[1] = 0;

    que.push(make_pair(0,1));
    while(!que.empty()) {
        int x=que.top().second;
        que.pop();

        //判断当前点是否访问过，如果访问过就可以略过
        if(vis[x]) continue;
        //将当前点设置为已访问
        vis[x] = 1;

        for(long long i=p[x]; i; i=edge[i].next) {
            long long tmp=edge[i].to;
            if(dis[tmp]>dis[x]+edge[i].w) {
                dis[tmp]=dis[x]+edge[i].w;
                que.push(make_pair(-dis[tmp],tmp));
            }
        }
    }
}
void dijkstra1() {
    priority_queue<pair<long long,long long> >que1;
    //vis1初始化为0即可
    memset(vis1,0,sizeof(vis1));
    for(long long i=1; i<=n; i++)
        dis1[i]=inf;

    dis1[1]=0;

    //不必初始化vis1[1]
    //vis1[1] = 0;

    que1.push(make_pair(0,1));
    while(!que1.empty()) {
        long long x=que1.top().second;
        que1.pop();

        //判断当前点是否访问过，如果访问过就可以略过
        if(vis1[x]) continue;
        //将当前点设置为已访问
        vis1[x] = 1;

        for(long long i=p1[x]; i; i=edge1[i].next) {
            long long tmp=edge1[i].to;
            if(dis1[tmp]>dis1[x]+edge1[i].w) {
                dis1[tmp]=dis1[x]+edge1[i].w;
                que1.push(make_pair(-dis1[tmp],tmp));
            }
        }
    }
}
int main() {
    cin>>n>>m;
    memset(p,0,sizeof(p));
    while(m--) {
        long long u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
        add_edge1(v,u,w);
    }
    dijkstra();
    dijkstra1();
    long long cnt=0;
    for(int i=1; i<=n; i++)
        cnt+=dis[i]+dis1[i];
    cout<<cnt<<endl;
    return 0;
}

by wdzxghl @ 2020-10-13 12:08:38

@Eloik 谢谢dalao