#C231116C. 简单图(graph)
标签（Label）
- 最短路算法
- 观察+分析
前言（Front talk)
$\qquad$对每种情况进行枚举，分析，正解并不意味着就一定是所有情况的通解，也有可能是每种情况的解的总和。
网址（Website）
题目（Problem）
给一个 $n$ 个点 $m$ 条边的无向简单图，求 $1$ 到 $n$ 经过恰好 $k$ 条边的最短简单路。
对于所有数据，满足 $2\le n\le 10^6$；$1\le m, k\le 10^6$；$\min(n, m, k)\le 5$；$1\le w_i\le 10^8$ 。
题解（Solution）
补：简单路定义：没有重边，没有环，没有经过两次及以上的点。
对于 $n<k\ ||\ m<k$ ，答案一定为 $0$；
剩下的 $k$ 只有 $5$ 种，考虑分类讨论：
- $k==1$ 直接将点 $1$ 所有边枚举一遍，输出最小值即可。
- $k==2$ 将 $1$ 和 $n$ 的所有能通往的点枚举一遍，输出最小值即可。
- $k>=3$ 将 $1$ 和 $n$ 的所有能通往的点求出，直接暴力 $\verb!dfs!$ ，注意要记录不要走一个点两次，去掉直接连向 $1-n$ 的点，时间复杂度优于正解（至少快 $1$ 倍）。
代码（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;
}后续（Ending）
$\qquad$其实我的代码时间复杂度和题解相像，但是其实 $dis$ 数组可以在输入的时候就可以处理好，时间更优，也不用搞一个 $set$ 来去重（主要是因为我懒），这样最快的有跑 $5000ms$ 的（当然加了快读），题解大概 $23000ms$ ，我的代码大概 $20000ms$ 。而且题解的处理方式还要更复杂一点。
