Light_LE @ 2024-10-05 18:20:08
跑样例结果输出超级大
#include <bits/stdc++.h>
#define maxn 1000003
using namespace std;
struct Edge {
int v, w, next;
}edge1[maxn], edge2[maxn];
struct Data {
long long dis; int pos;
bool operator < (const Data &x) const {
return x.dis < dis;
}
};
int n, m, cnt1, cnt2, vis[maxn], head1[maxn], head2[maxn];
long long dis[maxn], ans;
priority_queue<Data> q;
void add1(int u, int v, int w) {
cnt1++;
edge1[cnt1].v = v;
edge1[cnt1].w = w;
edge1[cnt1].next = head1[u];
head1[u] = cnt1;
}
void add2(int u, int v, int w) {
cnt2++;
edge2[cnt2].v = v;
edge2[cnt2].w = w;
edge2[cnt2].next = head2[u];
head2[u] = cnt2;
}
void dijkstra(int start, Edge edge[], int head[]) {
memset(dis, 0x7f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[start] = 0;
q.push((Data){0, start});
while (q.size()) {
Data f = q.top(); q.pop();
int pos = f.pos;
if (vis[pos]) {
continue;
}
vis[pos] = 1;
for (int i = head[pos]; i; i = edge[i].next) {
int v = edge[i].v, w = edge[i].w;
if (dis[v] > dis[pos] + w) {
dis[v] = dis[pos] + w;
if (dis[v] == 0) {
q.push((Data){dis[v], v});
}
}
}
}
}
int main() {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add1(u, v, w);
add2(v, u, w);
}
dijkstra(1, edge1, head1);
for (int i = 1; i <= n; i++) {
ans += dis[i];
}
// 初始化
dijkstra(1, edge2, head2);
for (int i = 1; i <= n; i++) {
ans += dis[i];
}
cout << ans;
return 0;
}
by Light_LE @ 2024-10-05 18:34:43
找到,应该把if (dis[v] == 0)
改为if (vis[v] == 0)
我真是个小丑