题解：AT_abc245_g [ABC245G] Foreign Friends

wangziming1202 · 2026-08-07 23:56:03 · 题解

题目详情

题目大意

给一张 n 个点、m 条边的无向带权图。

• 每个点 i 有一个颜色/国家 a_i。
• 有 𝑙 个特殊点。
• 对于每个点 i，要求它到最近的、颜色和 a_i 不同的特殊点的最短距离。
• 如果不存在这样的特殊点，输出 -1。 也就是说 ans_i = \min_{b是特殊点且a_i\ne b_i} dis(i,b) ### 题目思路 这题可以看成一个**多源最短路问题**。

本题的次短路为来源颜色不同的第二短状态。

关于“次短路”更新：

1. 可以更新第一短
2. 可以更新第二短 ::::info[Code]

   #include<bits/stdc++.h>
   using namespace std;
   #define int long long
   const int N = 1e5+10, M = 2e5+10, INF = 0x3f3f3f3f3f3f3f3f;
   int n,m,k,l,cnt,pre[N],dis1[N],dis2[N],c1[N],c2[N],a[N],b[N];
   struct Edge{
   int from,to,next,val;
   }edge[M];
   void addEdge(int u, int v, int val){
   cnt++;
   edge[cnt].from = u;
   edge[cnt].to = v;
   edge[cnt].val = val;
   edge[cnt].next = pre[u];
   pre[u] = cnt;
   }
   struct Node{
   int x,d,col;
   friend bool operator < (Node A, Node B){
       return A.d > B.d;
   }
   };
   priority_queue<Node> pq;
   void Insert(int x, int d, int color){
   if(d < dis1[x]){
       if(color==c1[x]){
           dis1[x] = d, c1[x] = color;
       }
       else{
           dis2[x] = dis1[x], c2[x] = c1[x];
           dis1[x] = d, c1[x] = color;
       }
       pq.push({x,d,color});
   }
   else if(d<dis2[x]){
       if(color==c1[x]) return;
       else{
           dis2[x]=d, c2[x] = color;
           pq.push({x,d,color});
       }
   }
   }
   void Dijkstra(){
   memset(dis1,0x3f,sizeof(dis1));
   memset(dis2,0x3f,sizeof(dis2));
   for(int i=1;i<=l;i++) Insert(b[i], 0, a[b[i]]);
   while(!pq.empty()){
       Node nowP = pq.top(); pq.pop();
       int d = nowP.d, cur = nowP.x, col = nowP.col;
       bool valid = false;
       if(c1[cur]==col && dis1[cur]==d) valid = true;
       if(c2[cur]==col && dis2[cur]==d) valid = true;
       if(!valid) continue;
       for(int j = pre[cur];j;j=edge[j].next){
           int to = edge[j].to;
           Insert(to,d+edge[j].val, col);
       }
   }
   }
   signed main(){
   cin>>n>>m>>k>>l;
   for(int i=1;i<=n;i++) 
       cin>>a[i];
   for(int i=1;i<=l;i++) 
       cin>>b[i];
   for(int i=1,x,y,z;i<=m;i++){
       cin>>x>>y>>z;
       addEdge(x,y,z);
       addEdge(y,x,z);
   }
   Dijkstra();
   for(int i=1;i<=n;i++){
       int ans = INF;
       if(c1[i]!=0 && c1[i]!=a[i]) ans = dis1[i];
       else if(c2[i]!=0 && c2[i]!=a[i]) ans = dis2[i];
       if(ans == INF) cout<<-1<<' ';
       else cout<<ans<<' ';
   }
   return 0;
   }

::::