#C240302C. C-最短路

前言（Front talk)

$\qquad$这道题是个原题。

网址（Website）

题目详情 - C-最短路 - Super

题解 - C-最短路 - Super

题解（Solution）

$\qquad$相对于之前的那道题，这道题的时间更多，足足给了 $4s$ ，于是可以直接用 $dfs$ 深搜。由于有 $ min(n,m,k)≤5 $ 的限制，所以无论是哪种情况，暴力深搜的时间都是能过的。由于是简单路径，只需要用 $vst$ （意思为 $visit$ ）数组来记录有没有访问过当前点即可。

代码（Code）

暴力代码：

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 1012345;
bool ST;

vector<P> ft[N];
int n,m,k,ans=inf;

bitset<N> vst;
void dfs(int x,int w,int dis){
	if(w==k){
		if(x==n) ans=min(ans,dis);
		return;
	}if(dis>=ans || x==n) return;
	vst[x]=true;
	for(auto p:ft[x]){
		int y=p.first,v=p.second;
		if(vst[y]) continue;
		dfs(y,w+1,dis+v);
	}vst[x]=false;
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	string str("c");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n>>m>>k;int Tim = clock();
	For(i,1,m){
		int x=input(),y=input(),w=input();
		if(x==y) continue;
		ft[x].emplace_back(y,w);
		ft[y].emplace_back(x,w);
	}dfs(1,0,0);
	cout<<(ans>=inf?-1:ans)<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}

另一种暴力代码：

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
inline int input(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
const int inf = 0x3f3f3f3f;
const int N = 1012345;
vector<pair<int,int> > ft[N];
int n,m,k,ans=inf,dis[N][2];

bitset<N> vst;
void dfs_ans(int x,int step,int sum){	
	if(sum>=ans) return;
	if(step==k) return ans=min(ans,sum+dis[x][1]),void();
	vst[x]=true;
	for(auto p:ft[x]){
		int y=p.first,v=p.second;
		if(vst[y]) continue;	
		dfs_ans(y,step+1,sum+v);
	}vst[x]=false;
}
signed main(){
	string str("c");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	memset(dis,0x3f,sizeof dis);
	n=input(),m=input(),k=input();
	For(i,1,m){
		int x=input(),y=input(),v=input();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}if(k>5 || m<k || n<k) return printf("-1\n"),0;
	switch(k){
		case 1:{
			for(auto p:ft[1]){
				int y=p.first,v=p.second;
				if(y==n) ans=min(ans,v);
			}break;
		}
		case 2:{
			for(auto p:ft[1]){
				int y=p.first,v=p.second;
				dis[y][0]=min(dis[y][0],v);
			}for(auto p:ft[n]){
				int y=p.first,v=p.second;
				ans=min(dis[y][0]+v,ans);
			}break;
		}
		default:{
			set<int> s;
			for(auto p:ft[1]){
				int y=p.first,v=p.second;
				dis[y][0]=min(dis[y][0],v);
				if(y!=n) s.insert(y);
			}for(auto p:ft[n]){
				int y=p.first,v=p.second;
				dis[y][1]=min(dis[y][1],v);
			}vst[1]=vst[n]=true;
			for(auto x:s) dfs_ans(x,2,dis[x][0]);
			break;
		}
	}return printf("%d\n",ans>=inf?-1:ans),0;
}