NC24950（Telephone Lines ）

感受


思路


BFS+优先队列

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
const int maxm = 2e4 + 10;
struct edge{
    int v, nex, w;
}e[maxm];
int n, p, k, head[maxn], cnt;
void init(){
    cnt = 0;
    for(int i = 0; i <= n; i++){
        head[i] = -1;
    }
}
void add_edge(int u, int v, int w){
    e[cnt] = (edge){v, head[u], w};
    head[u] = cnt++;
}
bool vis[maxn];
void dfs(int u){
    if(vis[u]) return ;
    vis[u] = true;
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        dfs(v);
    }
}
int num[maxn];
struct node{
    int u; int used;
    bool operator < (const node& b)const{
        return used > b.used;
    }
};
void bfs(int u, int val){
    priority_queue<node> que;
    que.push((node){u, 0}); num[u] = 0;
    while(!que.empty()){
        node tmp = que.top(); que.pop();
        int u, v, w; u = tmp.u;
        if(vis[u]) continue;
        for(int i = head[u]; ~i; i = e[i].nex){
            v = e[i].v; w = e[i].w; if(vis[v]) continue;
            if(w > val){
                if(num[v] == -1 || num[v] > num[u] + 1){
                    num[v] = num[u] + 1;
                    que.push((node){v, num[v]});
                }
            }
            else{
                if(num[v] == -1 || num[v] > num[u]){
                    num[v] = num[u];
                    que.push((node){v, num[v]});
                }
            }
        }
        vis[u] = true;
    }
}
bool check(int b){
    bfs(n, b);
    return num[1] <= k;
}
void Init(){
    for(int i = 1; i <= n; i++){
        vis[i] = false; num[i] = -1;
    }
}

int main(){
    scanf("%d%d%d", &n, &p, &k);
    init();
    int u, v, w;
    while(p--){
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w); add_edge(v, u, w);
    }
    dfs(1);
    if(!vis[n]){
        puts("-1"); return 0;
    }
    int l = -1, r = 1e6, mid;
    while(r - l > 1){
        mid = (l + r) / 2;
        Init();
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%d\n", r);
    return 0;
}

BFS+deque

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
const int maxm = 2e4 + 10;
struct edge{
    int v, nex, w;
}e[maxm];
int n, p, k, head[maxn], cnt;
void init(){
    cnt = 0;
    for(int i = 0; i <= n; i++){
        head[i] = -1;
    }
}
void add_edge(int u, int v, int w){
    e[cnt] = (edge){v, head[u], w};
    head[u] = cnt++;
}
bool vis[maxn];
void dfs(int u){
    if(vis[u]) return ;
    vis[u] = true;
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        dfs(v);
    }
}
int num[maxn];
void bfs(int u, int val){
    deque<int> que;
    que.push_front(u); num[u] = 0;
    while(!que.empty()){
        int u = que.front(); que.pop_front();
        int v, w;
        if(vis[u]) continue;
        for(int i = head[u]; ~i; i = e[i].nex){
            v = e[i].v; w = e[i].w; if(vis[v]) continue;
            if(w > val){
                if(num[v] == -1 || num[v] > num[u] + 1){
                    num[v] = num[u] + 1;
                    que.push_back(v);
                }
            }
            else{
                if(num[v] == -1 || num[v] > num[u]){
                    num[v] = num[u];
                    que.push_front(v);
                }
            }
        }
        vis[u] = true;
    }
}
bool check(int b){
    bfs(n, b);
    return num[1] <= k;
}
void Init(){
    for(int i = 1; i <= n; i++){
        vis[i] = false; num[i] = -1;
    }
}

int main(){
    scanf("%d%d%d", &n, &p, &k);
    init();
    int u, v, w;
    while(p--){
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w); add_edge(v, u, w);
    }
    dfs(1);
    if(!vis[n]){
        puts("-1"); return 0;
    }
    int l = -1, r = 1e6, mid;
    while(r - l > 1){
        mid = (l + r) / 2;
        Init();
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%d\n", r);
    return 0;
}