cjh88939492 @ 2023-03-09 11:46:18
求大佬指点
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstring>
#include <algorithm>
#include<iomanip>
#include<queue>
#include<limits.h>
#define INF 1<<30;
using namespace std;
const long long u = 2000005;
int n, m, p;
long long dis1[u],dis2[u];
bool vis1[u], vis2[u];
int head1[u], head2[u], cnt1 = 1, cnt2 = 1;
struct node {
long long dis;
int pos;
bool operator<(const node& x)const {
return x.dis < dis;
}
};
struct edge {
int to;
int w;
int next;
}edge1[u], edge2[u];
inline void addedge1(int u, int v, long long z) {
edge1[cnt1].to = v;
edge1[cnt1].w = z;
edge1[cnt1].next = head1[u];
head1[u] = cnt1++;
}
inline void addedge2(int u, int v, long long z) {
edge2[cnt2].to = v;
edge2[cnt2].w = z;
edge2[cnt2].next = head2[u];
head2[u] = cnt2++;
}
inline void dijkstra1(int num) {
priority_queue<node> q;
memset(vis1, 0, sizeof(vis1));
memset(dis1, 0x3f, sizeof(dis1));
dis1[num] = 0;
q.push(node{ 0,num });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.pos, d = tmp.dis;
if (vis1[x]) {
continue;
}
vis1[x] = 1;
for (int i = head1[x]; i; i = edge1[i].next) {
int y = edge1[i].to;
if (dis1[y] > dis1[x] + edge1[i].w) {
dis1[y] = dis1[x] + edge1[i].w;
}
if (!vis1[y]) {
q.push(node{ dis1[y],y });
}
}
}
}
inline void dijkstra2(int num) {
priority_queue<node> q;
memset(vis2, 0, sizeof(vis2));
memset(dis2, 0x3f, sizeof(dis2));
dis2[num] = 0;
q.push(node{ 0,num });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.pos, d = tmp.dis;
if (vis2[x]) {
continue;
}
vis2[x] = 1;
for (int i = head2[x]; i; i = edge2[i].next) {
int y = edge2[i].to;
if (dis2[y] > dis2[x] + edge2[i].w) {
dis2[y] = dis2[x] + edge2[i].w;
}
if (!vis2[y]) {
q.push(node{ dis2[y],y });
}
}
}
}
int main() {
cin>>n>>m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin>>a>>b>>c;
addedge1(a, b, c);
addedge2(b, a, c);
}
dijkstra1(1);
dijkstra2(1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans += dis1[i] + dis2[i];
}
cout << ans;
return 0;
}
by KinoTsuki @ 2023-10-08 19:48:08
快读+ O2 @cjh88939492
by Lele_Programmer @ 2024-01-26 14:43:43
dij + 堆优化