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 Lele_Programmer @ 2024-01-26 14:49:07
@[Lele_Programmer](/user/961972) [可是为什么我的 dij 很稳](https://www.luogu.com.cn/record/138663625)
by xiaoshumiao @ 2024-01-26 14:49:13
@[xiaoshumiao](/user/1008513) 你代码怎么写的，我这份看似没啥问题
by Lele_Programmer @ 2024-01-26 14:50:06
@[xiaoshumiao](/user/1008513) 噢我是说不开 O2 的情况下
by Lele_Programmer @ 2024-01-26 14:50:36
@[Lele_Programmer](/user/961972) [关掉 O2 也行啊](https://www.luogu.com.cn/record/144457204)
```cpp
#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 xiaoshumiao @ 2024-01-26 14:54:13
额，我这份好像也差不多啊（（
```cpp
#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:10
@[xiaoshumiao](/user/1008513)
by Lele_Programmer @ 2024-01-26 14:56:40
在 $n\le 10^6$ 时，$\Theta(n\log n)$ 级别的算法显然是正确的，可以尝试优化一下代码常数
by Endline @ 2024-01-26 15:21:02
你可以去掉 `#define int long long`，只给需要 `long long` 的数组开 `long long`
by Endline @ 2024-01-26 15:23:15
@[Endline](/user/401052) 好的，感谢
by Lele_Programmer @ 2024-01-26 15:46:21