(悬一关)求分析时间,今天模拟赛dijk被卡了
  • 板块灌水区
  • 楼主mm1214
  • 当前回复3
  • 已保存回复4
  • 发布时间2024/10/24 14:48
  • 上次更新2024/10/24 17:01:26
查看原帖
(悬一关)求分析时间,今天模拟赛dijk被卡了
774258
mm1214楼主2024/10/24 14:48

代码1(通过):

int dijk(int s , int t , int lim) {
    if (lim < x[s]) return 1e18;
    vector<int> dis(n + 5 , 1e18); bitset<N> vis;
    priority_queue<pii , vector<pii> , greater<pii>> pq; pq.push(pair(0 , s));
    pii tmp; int u; while(!pq.empty()) {
        tmp = pq.top(); pq.pop(); u = tmp.second;
        if (vis[u]) continue;
        vis[u] = 1; dis[u] = tmp.first;
        for (const auto &v : G[u]) {
            if (dis[v.first] > dis[u] + v.second && x[v.first] <= lim) dis[v.first] = dis[u] + v.second , pq.push(pair(dis[u] + v.second , v.first));
        }
    }
    return dis[t];
}

代码2(未通过):

int dijk(int s , int t , int lim) {
    if (lim < x[s]) return 1e18;
    vector<int> dis(n + 5 , 1e18); bitset<N> vis;
    priority_queue<pii , vector<pii> , greater<pii>> pq; pq.push(pair(0 , s));
    pii tmp; int u; while(!pq.empty()) {
        tmp = pq.top(); pq.pop(); u = tmp.second;
        if (vis[u]) continue;
        vis[u] = 1; dis[u] = tmp.first;
        for (const auto &v : G[u]) {
            if (!vis[v.first] && x[v.first] <= lim) pq.push(pair(dis[u] + v.second , v.first));
        }
    }
    return dis[t];
}
2024/10/24 14:48
加载中...