题解：P7192 [COCI2007-2008#6] GEORGE

· · 题解

P7192 题解

题目难度： 普及+/提高。

实际难度：普及/提高-。

题目概括

给定一张 n 个节点，m 条边的无向图，以及 T 先生的行动轨迹。在 T 先生出发 k 分钟后 Luka 从 a 点出发，T 先生和 Luka 不能同时走一条路，求 Luka 从 a 点到 b 点的最短时间。

思路

这题的思路就是在 Dijkstra 算法的松弛操作上加一步，如果 Luka 要走的路 T 先生正在走，那就等待到 T 先生离开这条路再往前走。

那我们就要对每条路径的封锁时间进行预处理，用一个二位数组 T 来表示，T[i][j] 表示连接点 i 和点 j 的路径的开始封锁时间和结束封锁时间。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
const int inf=2147483647;
int n,m,a,b,k,g,cnt,f[maxn],vis[maxn],head[maxn],vis2[maxn],waitt=0; 
queue<int> way;
struct mrt{
    int st,ed;
}T[maxn][maxn];
struct edge{
    int to,next,w;
}v[20005];
struct edge2{
    int to,w;
};
vector <edge2> v2[maxn];
void add(int u,int v2,int w){
    v[++cnt].next=head[u];
    v[cnt].to=v2;
    v[cnt].w=w;
    head[u]=cnt;
} 
struct node{
    int d,fd;
    friend bool operator<(node a,node b){  
        return a.fd>b.fd;
    }
}tmp; 
priority_queue<node> q; 
void dij(int s){
    for(int i=1;i<=n;i++){f[i]=inf;}
    f[s]=k;
    tmp.d=s,tmp.fd=0; 
    q.push(tmp);
    while(!q.empty()){
        int u=q.top().d;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=v[i].next){
            if(f[v[i].to]>(long long)f[u]+v[i].w){
                if(f[u]>=T[u][v[i].to].st&&f[u]<T[u][v[i].to].ed){ //如果当前时间处于封锁时间内 
                    f[v[i].to]=f[u]+v[i].w+(T[u][v[i].to].ed-f[u]); //加上等待时间 
                }
                else f[v[i].to]=f[u]+v[i].w;
                tmp.fd=f[v[i].to],tmp.d=v[i].to; 
                q.push(tmp);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    cin>>a>>b>>k>>g;
    for(int i=1;i<=g;i++){
        int x;
        cin>>x;
        way.push(x);
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        //双向边 
        add(x,y,z);
        add(y,x,z);
        v2[x].push_back((edge2){y,z});
        v2[y].push_back((edge2){x,z});
    }
    int temp=0;
    //处理T数组 
    while(!way.empty()){
        int x=way.front();
        way.pop();
        T[x][way.front()].st=temp;
        T[way.front()][x].st=temp; //双向边 
        for(int i=0,sz=v2[x].size();i<sz;i++){
            if(v2[x][i].to==way.front()){
                T[x][way.front()].ed=T[x][way.front()].st+v2[x][i].w;
                T[way.front()][x].ed=T[x][way.front()].st+v2[x][i].w;
            }
        }
        temp=T[x][way.front()].ed;
    }   

    dij(a); 
    cout<<f[b]-k<<endl; //别忘了答案要减去两个人出发的时间差 
    return 0;
}