我发现Y总代码没贴,于是…
题目描述
重庆城里有 n 个车站,m 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接,从任何一个车站出发都可以经过一条或者多条公路到达其他车站,但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 1,他有五个亲戚,分别住在车站 a,b,c,d,e。
过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福。
怎样走,才需要最少的时间?
输入样例
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
输出样例
21
C++ 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=5e4+10,M=2e5+10;
int n,m,cnt;
int head[N],q[N],dist[6][N];
int source[6];
bool st[N];
struct nkl
{
int nex,pri,to;
}e[M];
inline void add(int x,int y,int z)
{
e[++cnt].nex=head[x];
e[cnt].to=y;
head[x]=cnt;
e[cnt].pri=z;
}
inline void spfa(int start,int dist[])
{
memset(dist,0x3f,N*4);
dist[start]=0;
int hh=0,tt=1;
q[0]=start;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
for (int i=head[t];i;i=e[i].nex)
{
int v=e[i].to;
if(dist[v]>dist[t]+e[i].pri)
{
dist[v]=dist[t]+e[i].pri;
if(!st[v])
{
st[v]=true;
q[tt++]=v;
if(tt==N) tt=0;
}
}
}
}
}
inline int dfs(int u,int start,int distance)
{
if(u==6) return distance;
int res=INF;
for (int i=1;i<=5;i++)
{
if(!st[i])
{
int nex=source[i];
st[i]=true;
res=min(res,dfs(u+1,i,distance+dist[start][nex]));
st[i]=false;
}
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
source[0]=1;
for (int i=1;i<=5;i++) scanf("%d",&source[i]);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
for (int i=0;i<6;i++) spfa(source[i],dist[i]);
printf("%d\n",dfs(1,0,0));
return 0;
}
总结
其实像这样的图论+dfs暴搜还是第一次见,而且方法的话也很朴素,同时每种算法的要求较高(因为要学会去创造)
TLE了呀
good
good good
%%%大佬