2025.7.1作业

ren_gao_zu · 2025-07-01 22:48:17 · 学习·文化课

P1462 通往奥格瑞玛的道路

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b,f[100005],daan=-1;
struct node{
    int v,w;
    bool operator < (const node &b) const
    {
        return b.w<w;
    }
};
vector<node>e[100005];
priority_queue<node>pq;
bool vis[100005];
int dis[100005];
void dij(int s,int xian){
    for(int i=1;i<=n;i++){
        dis[i]=1e18;
        vis[i]=0;
    }
    dis[s]=0;
    pq.push({s,0});
    while(pq.size()){
        node tt=pq.top();
        pq.pop();
        int u=tt.v;
        if(vis[u]==1)continue;
        vis[u]=1;
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].v,w=e[u][i].w;
            if(dis[v]>dis[u]+w&&f[v]<=xian){
                dis[v]=dis[u]+w;
                if(!vis[v])pq.push({v,dis[v]});
            }

        }
    }
}
bool check(int mid){
    dij(1,mid);
    if(dis[n]>b)return 0;
    return 1;
}
void erfen(){
    int mid,l=0,r=1e9+100000;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)){
            r=mid-1;
            daan=mid;
        }
        else l=mid+1;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)cin>>f[i];
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        e[y].push_back({x,z});
    }
    erfen();
    if(daan==-1)cout<<"AFK";
    else cout<<daan;
    return 0;
}

P1339 [USACO09OCT] Heat Wave G

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,s,t,dis[100005];
struct node{
    int u,v,w;
}e[100005];

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=n;i++){
        dis[i]=1e18;
    }
    dis[s]=0;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
        e[i+m].u=e[i].v,e[i+m].v=e[i].u,e[i+m].w=e[i].w;
    }
    while(1){
        bool flag=0;
        for(int i=1;i<=m*2;i++){
            int u=e[i].u,v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w){
                flag=1;
                dis[v]=dis[u]+w;
            }
        }
        if(flag==0)break;
    }
    cout<<dis[t];
    return 0;
}

T_abc362_d [ABC362D] Shortest Path 3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,s,dis[200005],dian[200005];
bool vis[200005];
struct node{
    int v,w;
    bool operator < (const node &b) const 
    {
        return b.w<w;
    }
};
vector<node>e[200005];
priority_queue<node>pq;
void dij(){
    pq.push({1,dis[1]});
    while(pq.size()){
        node tt=pq.top();
        pq.pop();
        int u=tt.v;
        if(vis[u]==1)continue;
        vis[u]=1;   
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].v,w=e[u][i].w;
            if(dis[v]>dis[u]+w+dian[u]){
                dis[v]=dis[u]+w+dian[u];
                if(!vis[v])pq.push({v,dis[v]});
            }

        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(dis,0x3f,sizeof dis);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int ab;
        cin>>ab;
        dian[i]=ab;
        if(i==1)dis[i]=ab;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
    }
    dij();
    for(int i=2;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}