洛谷题解UVA最短路题解：UVA1112 Mice and Maze
xyx404
前言：
本题数据范围不大，使用 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";
}
return 0;
}
|
