社区讨论

链式前向星 + 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 条回复,欢迎继续交流。

正在加载回复...