- 题目描述
链接：https://ac.nowcoder.com/acm/contest/39100/F
来源：牛客网
阿宁打算下次放假去游玩。一共有 n 个城市， 阿宁住在 1 号城市，去到 n 号城市游玩。
城市有两种属性，一种是炎热，另一种是酷寒，每个城市是其中一种。从一个城市前往另一个城市，如果要前往的城市和当前城市的属性相同，则需要 x 时间，否则需要 y 时间。
阿宁可以使用倒转膜法，该膜法可以使所有城市（除了阿宁当前所在的城市）的属性变化（炎热变酷寒，酷寒变炎热），花费 z 时间。倒转膜法可以使用任意次。
阿宁想尽快去到 n 号城市游玩，她想知道她最少需要多少时间到达目的地？
- 题目分析
使用倒转魔法的时候会改变除自己以外所有城市的属性，这个魔法只会影响我们走到当前这个城市的时候所做出的决策，当我们走到其他城市的时候，由于其他城市的属性都被改变了，从这个城市(其他城市之一)走到另一个城市(其他城市之一)的决策没有被影响。所以只需要特殊建边最后跑一个最短路就可以了。
建边方法：边的权值 = min(x,y+z)或min(y,x+z) - ac代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z;
int u,v;
int a[200020];
int cnt;
struct ty2{
int num;
long long dist;
};
priority_queue<ty2> q;
bool operator<(const ty2 &a,const ty2 &b){
return a.dist>b.dist;
}
struct ty1{
int st;
int to;
int len;
int next;
}edge[600010];
int head[200010];
int vis[200010];
long long dis[200010];
void add(int x,int y,int v){
edge[++cnt].st = x;
edge[cnt].to = y;
edge[cnt].len = v;
edge[cnt].next = head[x];
head[x] = cnt;
}
long long dij(){
dis[1] = 0;
q.push({1,0});
while(!q.empty()){
auto p = q.top();
q.pop();
// cout<<p.num<<endl;
if(p.num==n) return p.dist;
if(vis[p.num]) continue;
vis[p.num] = 1;
for(int i = head[p.num];i!=-1;i = edge[i].next){
// cout<<edge[i].st<<" "<<edge[i].to<<" "<<dis[edge[i].st]+edge[i].len<<" "<<dis[edge[i].to]<<endl;
if(vis[edge[i].to]||dis[edge[i].st]+edge[i].len>dis[edge[i].to]) continue;
// cout<<dis[edge[i].to]<<endl;
dis[edge[i].to] = dis[edge[i].st]+edge[i].len;
q.push({edge[i].to,dis[edge[i].to]});
}
}
return -1;
}
int main(){
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
cin>>n>>m>>x>>y>>z;
for(int i = 1;i<=n;i++) cin>>a[i];
while(m--){
cin>>u>>v;
if(a[u]==a[v]){
add(u,v,min(x,y+z));
add(v,u,min(x,y+z));
}
else{
add(u,v,min(y,x+z));
add(v,u,min(y,x+z));
}
}
cout<<dij();
}