正解时间复杂度？

Lele_Programmer @ 2024-01-26 14:47:36

by Lele_Programmer @ 2024-01-26 14:49:07

AC: https://www.luogu.com.cn/record/144454379

TLE #1 #3

https://www.luogu.com.cn/record/144454737

TLE #2

https://www.luogu.com.cn/record/144453382

by xiaoshumiao @ 2024-01-26 14:49:13

@Lele_Programmer 可是为什么我的 dij 很稳

by Lele_Programmer @ 2024-01-26 14:50:06

@xiaoshumiao 你代码怎么写的，我这份看似没啥问题

by Lele_Programmer @ 2024-01-26 14:50:36

@xiaoshumiao 噢我是说不开 O2 的情况下

by xiaoshumiao @ 2024-01-26 14:54:13

@Lele_Programmer 关掉 O2 也行啊

#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=1000005,MAXM=1000005,INF=0x3f3f3f3f;
int head[2][MAXN],d[MAXN],cnt;
bool vis[MAXN];
struct Edge {
  int end,val,next;
}edge[2*MAXM];
struct Node {
  int num,dis;
  bool operator <(const Node &x) const {
    return dis>x.dis;
  }
};
void add(int u,int v,int w,int t) {
  edge[++cnt].next=head[t][u];
  edge[cnt].end=v;
  edge[cnt].val=w;
  head[t][u]=cnt;
}
void dijkstra(int n,int s,int t) {
  for(int i=1;i<=n;i++) {
    d[i]=INF;
    vis[i]=false;
  }
  d[s]=0;
  priority_queue<Node>q;
  q.push((Node){s,0});
  while(!q.empty()) {
    Node p=q.top();
    q.pop();
    if(vis[p.num])
      continue;
    vis[p.num]=true;
    for(int i=head[t][p.num];i!=0;i=edge[i].next) {
      if(!vis[edge[i].end]&&d[p.num]+edge[i].val<d[edge[i].end]) {
        d[edge[i].end]=d[p.num]+edge[i].val;
        if(!vis[edge[i].end])
          q.push((Node){edge[i].end,d[edge[i].end]});
      }
    }
  }
}
int main() {
  int n,m,u,v,w;
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++) {
    scanf("%d %d %d",&u,&v,&w);
    add(u,v,w,0);
    add(v,u,w,1);
  }
  dijkstra(n,1,0);
  long long sum=0;
  for(int i=1;i<=n;i++)
    sum+=d[i];
  dijkstra(n,1,1);
  for(int i=1;i<=n;i++)
    sum+=d[i];
  printf("%lld",sum);
  return 0;
}

by Lele_Programmer @ 2024-01-26 14:56:10

额，我这份好像也差不多啊（（

#include <bits/stdc++.h>

#define int long long
#define inf 1000000000000000000LL

using namespace std;

const int N=1000005;
const int M=1000005;

int n,m;
int e[M],ne[M],w[M],h[N],tot;
int e2[M],ne2[M],w2[M],h2[N],tot2;
int a,b,c;
int dis1[N],dis2[N];
bool check1[N],check2[N];

typedef pair<int,int> pii;

priority_queue< pii,vector<pii>,greater<pii> > q;

void add(int a,int b,int c) {
    e[tot]=b,w[tot]=c,ne[tot]=h[a],h[a]=tot++;
}

void add2(int a,int b,int c) {
    e2[tot2]=b,w2[tot2]=c,ne2[tot2]=h2[a],h2[a]=tot2++;
}

void dijkstra_1() {
    for (int i=1;i<=n;++i) dis1[i]=inf,check1[i]=false;
    dis1[1]=0;
    q.push(make_pair(dis1[1],1));
    while (!q.empty()) {
        auto tp=q.top(); q.pop();
        int curr=tp.second;
        check1[curr]=true;
        for (int i=h[curr];~i;i=ne[i]) {
            if (dis1[e[i]]>dis1[curr]+w[i] && !check1[e[i]]) {
                dis1[e[i]]=dis1[curr]+w[i];
                q.push(make_pair(dis1[e[i]],e[i]));
            }
        }
    }
}

void dijkstra_2() {
    for (int i=1;i<=n;++i) dis2[i]=inf,check2[i]=false;
    dis2[1]=0;
    q.push(make_pair(dis2[1],1));
    while (!q.empty()) {
        auto tp=q.top(); q.pop();
        int curr=tp.second;
        check2[curr]=true;
        for (int i=h2[curr];~i;i=ne2[i]) {
            if (dis2[e2[i]]>dis2[curr]+w2[i] && !check2[e2[i]]) {
                dis2[e2[i]]=dis2[curr]+w2[i];
                q.push(make_pair(dis2[e2[i]],e2[i]));
            }
        }
    }
}

signed main() {
    memset(h,-1,sizeof(h));
    memset(h2,-1,sizeof(h2));
    scanf("%lld %lld",&n,&m);
    while (m--) {
        scanf("%lld %lld %lld",&a,&b,&c);
        add(a,b,c); add2(b,a,c);
    }
    dijkstra_1();
    dijkstra_2();
    int ans=0;
    for (int i=1;i<=n;++i) {
        ans+=dis1[i]+dis2[i];
    }
    printf("%lld",ans);
    return 0;
}

by Lele_Programmer @ 2024-01-26 14:56:40

@xiaoshumiao

by Endline @ 2024-01-26 15:21:02

在 n\le 10^6 时，\Theta(n\log n) 级别的算法显然是正确的，可以尝试优化一下代码常数

by Endline @ 2024-01-26 15:23:15

你可以去掉 #define int long long，只给需要 long long 的数组开 long long

by Lele_Programmer @ 2024-01-26 15:46:21

@Endline 好的，感谢