NC20675. MIKU酱的氪金宝典
描述
输入描述
多组输入，每个样例第一行输入两个整数n,m(2<=n<=200,1<=m<=1000)表示关卡和规则的数量，接下来m行规则，每行输入x,y,w（w<=1000）,表示从关卡x到y需要缴纳w的费用，保证题目有解，不会出现x=y的情况
输出描述
输出一行，代表最少的钱
示例1
输入:
4 4 1 2 2 1 3 1 2 4 3 3 4 1
输出:
1
C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 564K, 提交时间: 2020-08-10 00:31:06
#include<bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int dp[205][205];
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,m;
while(cin>>n>>m){
memset(dp,0x3f,sizeof dp);
int x,y,w;
while(m--){
cin>>x>>y>>w;
if(w<dp[x][y])dp[x][y]=w;
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));
cout<<dp[1][n]<<'\n';
}
}