求为什么TLE
查看原帖
求为什么TLE
1311804
zhiqin__楼主2025/1/1 01:09

rt,在本地是正常输出的

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

const int N = 1e5 + 5;
vector<vector<int>> e;
int dis[N];
bool vis[N];

void dij(int s) {
    for (int i=0; i<N; i++) dis[i] = 1e9;
    priority_queue<pair<int, int>> q;
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (!vis[u]) {
            vis[u] = 1;
            for (int p : e[u]) {
                if (dis[p] > dis[u] + 1) {
                    dis[p] = dis[u] + 1;
                    q.push({-dis[p], p});
                }
            }
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d\n", &m, &n);
    e.resize(n+1);
    while (m--) {
        int t = 0;
        vector<int> p;
        char c;
        c = getchar();
        while (c != '\n') {
            if (c == ' ') {
                p.push_back(t);
                t = 0;
            }
            else {
                t = t * 10 + (c - '0');
            }
            c = getchar();
        }
        p.push_back(t);
        for (int i=0; i<p.size()-1; i++) {
            for (int j=i+1; j<p.size(); j++) {
                e[p[i]].push_back(p[j]);
            }
        }
        
    }
    dij(1);
    printf("%d\n", dis[n] - 1);
}
2025/1/1 01:09
加载中...