56分求调
查看原帖
56分求调
1654113
cqbz_csp楼主2025/7/1 21:53
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;
int n,m,k,s,p,q,c[100005],h[100005];
long long a[100005];
vector<int>b[100005];
int main(){
    cin>>n>>m>>k>>s>>p>>q;
    for (int i=1;i<=n;i++)a[i]=p;//初始化每个城市价格全部为安全城市价格q
    for (int i=1;i<=n;i++)h[i]=-1;//初始化1城市到1~n城市的价格为-1
    for (int i=1;i<=k;i++)cin>>c[i];
    for (int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        b[u].push_back(v);
        b[v].push_back(u);
    }
    for (int i=1;i<=k;i++){
        queue<pair<int,int> >q1;
        unordered_set<int>d;
        q1.push({c[i],0});
        while(!q1.empty()){//bfs将危险城市价格全部设为1
            pair<int ,int>it=q1.front();
            q1.pop();
            if (d.count(it.first))continue;//判断此城市是否由于已入侵城市c[i]标记为危险城市
            d.insert(it.first);
            if (it.second>s)continue;
            a[it.first]=q;
            for (int i=0;i<b[it.first].size();i++){
                q1.push({b[it.first][i],it.second+1});
            }
        }
        a[c[i]]=-1;//将被僵尸控制城市价格设为-1
    }
    queue<pair<int ,int> >q2;
    q2.push({1,0});
    while(!q2.empty()){//bfs求出1城市到每个城市的最小花费
        pair<int ,int>it=q2.front();
        q2.pop();
        if (a[it.first]==-1)continue;
        if (h[it.first]<=it.second&&h[it.first]!=-1)continue;
        h[it.first]=it.second;
        for (int i=0;i<b[it.first].size();i++){
            q2.push({b[it.first][i],it.second+a[b[it.first][i]]});
        }
    }
    cout<<h[n]-a[n];//由于h[n]bfs中包含了a[n],所以减去a[n]
}
2025/7/1 21:53
加载中...