NC253330题解

看到有人用dfs求最短路，，我们可以看到这道题一共四个点所以n<=4，我们可以使用floyd算法来求最短路

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int f[10][10];
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	std::cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=6;i++){
		for(int j=1;j<=6;j++){
			f[i][j]=INT_MAX;//初始化 
		}
	} 
	f[1][2]=n;//坐大巴到小山路西的时间
	f[1][3]=n;//坐大巴到小山路西的时间
	f[2][4]=m;//小山路西走路到公司的时间 
	f[3][4]=k;//坐车要的时间
	for(int u=1;u<=4;u++){
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				//cout<<f[i][j]<<endl;
				f[i][j]=min(f[i][j],f[i][u]+f[u][j]);
			}
		}
	}
	cout<<f[1][4];
	return 0;
}