社区讨论
就打算过个k = 0的情况,咋还TLE了?
P14318「ALFR Round 11」B 行走 (walk)参与者 6已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @mhizs8f6
- 此快照首次捕获于
- 2025/11/03 18:23 4 个月前
- 此快照最后确认于
- 2025/11/03 18:23 4 个月前
如题,用的是SPFA算法多次计算最短路径,因为k = 0,所以直接计算两个最短路径加和就好了,但不知道为什么超时了,题解里就是这样的思路呀。
(先叠个甲,本人蒟蒻,刚学图和最短路径没多久求,大佬指点,悬关)
CPP#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef long long ll;
int t, a, b, c, d, cnt;
int n, m, k;
struct edge
{
int to, val, nxt;
}e[MAXN];
int dis[MAXN], head[MAXN], vis[MAXN];
void add(int u, int v, int w)
{
e[++cnt].to = v, e[cnt].val = w, e[cnt].nxt = head[u];
head[u] = cnt;
}
void SPFA(int s)
{
queue<int> q;
q.push(s), vis[s] = 1, dis[s] = 0;
while(!q.empty())
{
int f = q.front(); q.pop(), vis[f] = 0;
for(int i = head[f]; i; i = e[i].nxt)
{
int v = e[i].to, w = e[i].val;
if(dis[v] > dis[f] + w)
{
dis[v] = dis[f] + w;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
int main()
{
cin >> t;
if(t > 10) return 0;
while(t--)
{
ll ans = 0;
cin >> n >> m >> k;
for(int i = 1; i <= m; i++)
{
cin >> a >> b;
add(a, b, 1), add(b, a, 1);
}
cin >> a >> b >> c >> d;
memset(dis, 0x3f3f3f3f, sizeof(dis));
SPFA(a);
ans += dis[b];
memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
SPFA(c);
ans += dis[d];
cout << ans << ".000000000000" << endl; // 偷懒了,但估计不是因为这个超时的
memset(vis, 0, sizeof(vis));
}
return 0;
}
回复
共 8 条回复,欢迎继续交流。
正在加载回复...