求助P1462

dino @ 2023-02-23 12:53:44

#include<bits/stdc++.h>
using namespace std;
int const N = 1e4 + 5;
long long const MAX = 1e9;
int n, m, b;
vector<pair<long long, long long> > a[N];
long long dis[N];
bool vis[N];
long long s[N];

bool dijkstra(long long y){
    if(y < s[1]) return 0;
    for(int i = 1; i <= n; i++) dis[i] = MAX;
    dis[1] = 0;
    for(int i = 1; i <= n; i++) vis[i] = 0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > q;
    q.push(make_pair(0, 1));
    while(!q.empty()){
        long long x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < a[x].size(); i++)
        {
            long long u = a[x][i].first, v = a[x][i].second;
            if(s[i] <= y && (dis[u] > dis[x] + v) && vis[u] == 0)
            {
                dis[u] = dis[x] + v;
                q.push(make_pair(dis[u], u));
            }
        }
    }
    cout << dis[n];
    if(dis[n] < b)
        return 1;
    return 0;
}

int main(){
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= m; i++){
        int t, u, v;
        cin >> t >> u >> v;
        a[t].push_back(make_pair(u, v));
        a[u].push_back(make_pair(t, v));
    }
    long long l = 1, r = MAX;
    if(dijkstra(MAX) == 0){
        cout << "AFK";
        return 0;
    }
    while(l <= r){
        long long mid = (l + r) / 2;
        if(dijkstra(mid))
            r = mid - 1;
        else
            l = mid + 1; 
    } 
    cout << l;
    return 0;
}

by dino @ 2023-02-23 12:59:25

    cout << dis[n];

这一行排错用的，可忽略

by ACRUSHj @ 2023-02-23 13:31:32

@dino

帮你改了 30pts，去上学力

#include<bits/stdc++.h>
using namespace std;
int const N = 1e4 + 5;
long long const MAX = 1e18;
int n, m, b;
vector<pair<long long, long long> > a[N];
long long dis[N];
bool vis[N];
long long s[N];

bool dijkstra(long long y){
    if(s[1]>y) return 0;
    for(int i = 1; i <= n; i++) dis[i] = MAX;
    dis[1] = 0;
    for(int i = 1; i <= n; i++) vis[i] = 0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > q;
    q.push(make_pair(0, 1));
    while(!q.empty()){
        long long x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < a[x].size(); i++)
        {
            long long u = a[x][i].first, v = a[x][i].second;
            if(s[i] <= y && (dis[u] > dis[x] + v) && vis[u] == 0)
            {
                dis[u] = dis[x] + v;
                q.push(make_pair(dis[u], u));
            }
        }
    }
    //cout << dis[n];
    if(dis[n]>b)return 0;
    return 1;
}

int main(){
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= m; i++){
        long long t, u, v;
        cin >> t >> u >> v;
        a[t].push_back(make_pair(u, v));
        a[u].push_back(make_pair(t, v));
    }
    long long l = 0, r = MAX;
    if(dijkstra(MAX) == 0){
        cout << "AFK";
        return 0;
    }
    while(l < r){
        long long mid = (l + r) / 2ll;
        if(dijkstra(mid))
            r = mid - 1;
        else
            l = mid; 
    } 
    cout << l;
    return 0;
}

by 035966_L3 @ 2023-02-23 14:51:10

@dino 第 26 行中 s[i] 应为 s[u]。

又切了一题！

by ACRUSHj @ 2023-02-23 17:50:39

过了：

#include<bits/stdc++.h>
using namespace std;
int const N = 1e4 + 5;
long long const MAX = 1e18;
int n, m, b;
vector<pair<long long, long long> > a[N];
long long dis[N];
bool vis[N];
long long s[N];

bool dijkstra(long long y){
    if(s[1]>y) return 0;
    for(int i = 1; i <= n; i++) dis[i] = MAX;
    dis[1] = 0;
    for(int i = 1; i <= n; i++) vis[i] = 0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > q;
    q.push(make_pair(0, 1));
    while(!q.empty()){
        long long x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < a[x].size(); i++)
        {
            long long u = a[x][i].first, v = a[x][i].second;
            if(s[u] <= y && (dis[u] > dis[x] + v) && vis[u] == 0)
            {
                dis[u] = dis[x] + v;
                q.push(make_pair(dis[u], u));
            }
        }
    }
    //cout << dis[n];
    if(dis[n]>b)return 0;
    return 1;
}

int main(){
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= m; i++){
        long long t, u, v;
        cin >> t >> u >> v;
        a[t].push_back(make_pair(u, v));
        a[u].push_back(make_pair(t, v));
    }
    long long l = 0, r = MAX;
    if(dijkstra(MAX) == 0){
        cout << "AFK";
        return 0;
    }
    while(l < r){
        long long mid = (l + r) / 2ll;
        if(dijkstra(mid))
            r = mid;
        else
            l = mid+1; 
    } 
    cout << l;
    return 0;
}

by ACRUSHj @ 2023-02-23 18:30:35

@wosizmcy 这都能得 30 属实是没想到

by dino @ 2023-02-24 12:21:35

谢谢各位大佬