题解：P8068 [BalticOI 2002] Bicriterial routing (Day2)

· · 题解

模拟赛考了这道题，然后场切了。认为评蓝虚高。

做法

如果 t 相同，显然 c 越小越好。然后我们对于每个固定的 t，都求出最小的花费 c。求完之后从小到大遍历每个 t，如果当前的花费严格小于之前的最小值，就是“最短路径”。

其中这个最小花费可以通过类似分层图的方法求。设计 T\times n+u 表示使用 T 的时间到达 u 的花费最小值。把上面的 T\times n+u 当成点的编号，求起点为 0\times n+s 的单源最短路。

在最优情况下，一条路径最多只经过每个点一次。题目说 n\le 100，t\le 100，所以当 T>10000 时停止即可。

代码

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
    int x=0,y=1;
    char e=getchar();
    while(e<'0'||e>'9') {
        if(e=='-')y=-1;
        e=getchar();
    }
    while(e>='0'&&e<='9') {
        x=(x<<1)+(x<<3)+(e^'0');
        e=getchar();
    }
    return x*y;
}
const int N=105;
int n,m,s,e,ans;
struct node {
    int v,c,t;
};
vector<node>G[N];
int dis[1000105];
//对于固定的时间，花费最小是多少 
bool vis[1000105];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
signed main() {
    R(n),R(m),R(s),R(e);
    for(int i=1; i<=m; ++i) {
        int R(u),R(v),R(c),R(t);
        G[u].push_back({v,c,t});
        G[v].push_back({u,c,t});
    }
    memset(dis,0x3f,sizeof dis);
    q.push({0,s});
    dis[s]=0;
    while(!q.empty()) {
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        int tu=(u-1)/n;
//      cout<<tu<<" "<<u-tu*n<<"\n";
        int real_u=u-tu*n;
        for(auto piii:G[real_u]) {
            int v=piii.v,c=piii.c,t=piii.t+tu;
            if(t>10000){
                continue;
            }
            if(dis[t*n+v]>dis[u]+c) {
//              cout<<"[";
//              cout<<v<<"]";
                dis[t*n+v]=dis[u]+c;
                q.push({dis[t*n+v],t*n+v});
            }
        }
    }
    int mini=0xccfccfccfccfccf;
    for(int t=0; t<=10000; ++t) {
        if(dis[t*n+e]>1e14)continue;
        if(dis[t*n+e]<mini) {
            mini=dis[t*n+e];
            ++ans;
        }
    }
    cout<<ans<<"\n";
    return 0;
}