#C231116C. 简单图(graph)

前言（Front talk)

对每种情况进行枚举，分析，正解并不意味着就一定是所有情况的通解，也有可能是每种情况的解的总和。

网址（Website）

题目详情 - 简单图(graph) - Super

题解 - 简单图(graph) - Super

题目（Problem）

给一个个点条边的无向简单图，求到经过恰好条边的最短简单路。

对于所有数据，满足；；；。

题解（Solution）

补：简单路定义：没有重边，没有环，没有经过两次及以上的点。

对于，答案一定为；

剩下的只有种，考虑分类讨论：

直接将点所有边枚举一遍，输出最小值即可。
将和的所有能通往的点枚举一遍，输出最小值即可。
将和的所有能通往的点求出，直接暴力，注意要记录不要走一个点两次，去掉直接连向的点，时间复杂度优于正解（至少快倍）。

代码（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;
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;	
//		printf("%d %d %d %d %d\n",x,y,v,step,sum);
//		if(step+1==k) {ans=min(ans,sum+v+dis[y][1]);continue;}
		dfs_ans(y,step+1,sum+v);
	}vst[x]=false;
}
signed main(){
	string str("graph");
	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;
}