社区讨论

就打算过个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 条回复,欢迎继续交流。

正在加载回复...