社区讨论
链式前向星 + dijkstra 为什么只有30分?
P1629邮递员送信参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo7jx2ar
- 此快照首次捕获于
- 2023/10/27 03:02 2 年前
- 此快照最后确认于
- 2023/10/27 03:02 2 年前
rt,代码如下,带有2编号的都是反图。
CPP#include<cstdio>
#include<queue>
#define maxn 10010
#define maxm 100010
#define inf 0x3f
#define pii pair<int, int>
using namespace std;
int n, m, u, v, w;
bool vis[maxn], vis2[maxn];
int cnt, cnt2, head[maxn], head2[maxn];
long long dis[maxn], dis2[maxn], ans;
priority_queue<pii> q, q2;
struct egde
{
int to, next, val;
}eg[maxm], eg2[maxm];
void add(int u, int v, int w)
{
eg[++cnt].to = v, eg[cnt].val = w;
eg[cnt].next = head[u], head[u] = cnt;
}
void add2(int u, int v, int w)
{
eg2[++cnt2].to = v, eg2[cnt2].val = w;
eg2[cnt2].next = head2[u], head2[u] = cnt2;
}
void dijkstra(int s)
{
q.push({0, s}), dis[s] = 0;
while(!q.empty())
{
int top = q.top().second; q.pop();
if (vis[top]) continue;
else vis[top] = 1;
for (int i = head[top]; i; i = eg[i].next)
{
int t = eg[i].to;
if (dis[t] > eg[i].val + dis[top])
{
dis[t] = eg[i].val + dis[top];
q.push({-dis[t], t});
}
}
}
}
void dijkstra2(int s)
{
q2.push({0, s}), dis2[s] = 0;
while(!q2.empty())
{
int top = q2.top().second; q2.pop();
if (vis2[top]) continue;
else vis2[top] = 1;
for (int i = head2[top]; i; i = eg2[i].next)
{
int t = eg2[i].to;
if (dis2[t] > dis2[top] + eg2[i].val)
{
dis2[t] = dis2[top] + eg2[i].val;
q2.push({-dis2[t], t});
}
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &u, &v, &w);
add(u, v, w), add2(v, u, w);
}
for (int i = 1; i <= n; i++)
dis[i] = dis2[i] = inf;
dijkstra(1); dijkstra2(1);
for (int i = 2; i <= n; i++)
ans += dis[i] + dis2[i];
printf("%lld", ans);
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...