题解：UVA1112 Mice and Maze

xyx404 · 2025-07-01 16:47:33 · 题解

前言：

本题数据范围不大，使用 Floyd 也可通过，但本人练习迪杰斯特拉，所以写的是迪杰斯特拉建反图的题解。

题意：

有 n 个点，求有多少个点到 e 点的最小花费小于等于 t。

有多组数据。

思路：

可以发现起点有很多个，但是终点只有一个，我们可以考虑建反图，把终点看做反图起点，然后跑迪杰斯特拉得出终点到每个点的最小花费，然后把花费小于等于 t 的点的个数加起来就好了。

输出格式注意。

UVA 的输出格式是谜，本题输出要求每次输出答案后换行，如果这不是最后一组数据，则需要再换一次行；但是如果是最后一组数据则只需要换一次行。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int T,n,e,t,m;
int a,b;
LL c;
bool vis[120];
LL dis[120];
struct node{
    int now;LL v;
    friend bool operator <(node x,node y){
        return x.v>y.v;
    }
};
struct nod{
    int to;
    LL val;
};
priority_queue<node>dl;
vector<vector<nod> >tu;
void dij(int s){
    memset(dis,127,sizeof dis);
    memset(vis,0,sizeof vis);
    dl.push({s,0});
    dis[s]=0;
    while(dl.empty()==0){
        int now=dl.top().now;
        LL v=dl.top().v;
        dl.pop();
        if(vis[now])continue;
        vis[now]=1;
        for(auto to:tu[now]){
            if(dis[to.to]>dis[now]+to.val){
                dis[to.to]=dis[now]+to.val;
                dl.push({to.to,dis[to.to]});
            }
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        tu.clear();
        tu.resize(120);
        cin>>n>>e>>t>>m;
        for(int i=1;i<=m;i++){
            cin>>a>>b>>c;
            tu[b].push_back({a,c});
        }
        dij(e);
        int ans=0;
        for(int i=1;i<=n;i++){
            if(dis[i]<=t)ans++;
        }
        cout<<ans<<"\n";
        if(T)cout<<"\n";// 一定要这样，不然 PE
    }
    return 0;
}