前言:我们再做一些最短路题目时候,往往会因为一些特殊限制导致建的边太多,所以我们建立一种虚拟点作为中转站,大大减少边数

1.HDU春季联赛10.小塔的梦境迷宫

题面:

对于走的边数为%3=0,%3=1,%3=2的情况,可以直接拆点,但是如果对于"瞬移"这种情况要建图,那最坏情况将会多见nn条边,所以我们建立不同属性的虚拟点,这样只会多建立2n条边.一个点进入对应属性的虚拟点需要cost 1的dis和x的金币,出来需要cost 0的dis和0的金币,这样就完成了题目

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db  double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
   if(fabs(x)<eps){
      return 0;
   }
   return x<0?-1:1;
}
void debug(){
   cout<<"Test:Wrong"<<'\n';
   exit(0);
}
struct node{
   int x,id,w;
   bool operator<(node p)const{
       return w>p.w;   
   }
};
struct adj{
    int y,id,w;
};
vector<adj>g[N];
int A[N];
int dis[N][3];
int vis[N][3];
void solve(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=1;i<=2*n;i++){
        g[i].clear();
        for(int j=0;j<3;j++){
            dis[i][j]=inf;
            vis[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>A[i];
        g[i].push_back({A[i]+n,0,0});
        g[A[i]+n].push_back({i,1,x});
    }  
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        g[x].push_back({y,1,w});
    }
    priority_queue<node>q;
    dis[1][0]=0;
    q.push({1,0,0});
    while(q.size()){
        auto[x,id,w]=q.top();
        q.pop();
        if(vis[x][id])continue;
        vis[x][id]=1;
        for(auto [y,add,ww]:g[x]){
             if(dis[y][(id+add)%3]>dis[x][id]+ww){
                dis[y][(id+add)%3]=dis[x][id]+ww;
                q.push({y,(id+add)%3,dis[y][(id+add)%3]});
             }
        }
    }
    if(dis[n][0]!=inf){
        cout<<dis[n][0]<<'\n'; 
    }else{
        cout<<-1<<'\n'; 
    }
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T=1;
  cin>>T;
  while(T--)solve();
  return 0;
}

2.Fast Travel Text Editor

链接

这道题朴素的想法就是类似上题,对每一对可以跳跃的点建边,但这样肯定会超时

所以我们依旧建立中转站,一共有26*26种中转站,从普通点进入中转站需要cost 1,从中转站进入普通点 cost0.

而对于每个询问,我们分成两种情况:(1)不使用跳跃操作,则距离就是两点之间的距离(2)使用跳越操作,我们枚举中转站,dis[中转站][s]+dis[中转站][t]+1必然是经过某一个中转站之时最小的s到t的距离,维护最小值即为答案.