spfa被卡掉了，估计堆优化的djk能行
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=50100;
int h[N],e[4*N],ne[4*N],w[4*N];
int idx;
int st[N];
int dist[6][N];
int n,m;
int x[N];
int s[6];
void add(int a,int b,int c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
void spfa(int start,int dist[])
{
dist[start]=0;
st[start]=1;
queue<int> q;
q.push(start);
while(q.size())
{
int t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
//cout<<"j "<<j<<" "<<dist[j]<<endl;
//cout<<w[i]<<endl;
if(dist[j]>dist[t]+w[i])
{
dist[j]=dist[t]+w[i];
//cout<<dist[j]<<endl;
if(!st[j])
{
q.push(j);
st[j]=1;
}
}
}
}
}
//当前拜访到了第u个亲戚，从start出发，以走了distance距离
int dfs(int u, int step, int distance)
{
if (step == 5)
{
// cout << u << " " << distance << endl;
return distance;
}
int res = 0x3f3f3f3f;
for (int i = 1; i < 6; i ++ )
{
//cout << st[i] << endl;
if (!st[i])
{
st[i] = 1;
res = min(res , dfs(i, step + 1, distance + dist[u][s[i]]));
st[i] = 0;
}
}
return res;
}
int main()
{
//memset(st,0,sizeof st);
memset(h,-1,sizeof h);
memset(dist,0x3f,sizeof dist);
cin>>n>>m;
for(int i=1;i<=5;i++)
{
cin>>s[i];
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
s[0]=1;
//从第0个亲戚(指佳佳）出发，到所有站的距离；一直做到第五个
for (int i = 0; i < 6; i ++ )
spfa(s[i], dist[i]);
//从1出发
memset(st,0,sizeof st);
cout<<dfs(0,0,0);
}
二刷，堆优化djk终于ac，注意dist数组不能开大，因此第一维要用序号代替点的编号
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
const int N=100010,M=200010;
int st[N],e[M],ne[M],h[N],w[M],idx,dist[7][N];
int res;
int p[N];
int pst[N];
int n,m;
void add(int a,int b,int c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
void djk(int s)
{
priority_queue<pii,vector<pii>,greater<pii>> heap;
memset(st,0,sizeof st);
//cout<<p[s]<<endl;
heap.push({0,p[s]});
dist[s][p[s]]=0;
while(heap.size())
{
auto t=heap.top();
heap.pop();
int ver=t.second;
int dis=t.first;
if(st[ver]) continue;
st[ver]=1;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[s][j]>dis+w[i])
{
dist[s][j]=dis+w[i];
heap.push({dist[s][j],j});
}
}
}
}
//ver是第几个邻居
void dfs(int ver,int step,int dis)
{
if(dis>=res)
{
return;
}
if(step==5)
{
res=dis;
return;
}
for(int i=1;i<=5;i++)
{
if(pst[p[i]]==0)
{
pst[p[i]]=1;
dfs(i,step+1,dis+dist[ver][p[i]]);
pst[p[i]]=0;
}
}
}
int main()
{
cin>>n>>m;
memset(dist,0x3f,sizeof dist);
memset(h,-1,sizeof h);
p[0]=1;
for(int i=1;i<=5;i++)
{
cin>>p[i];
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
//cout<<p[2];
for(int i=0;i<=5;i++)
{
djk(i);
}
res=0x3f3f3f3f;
dfs(0,0,0);
cout<<res;
return 0;
}
三刷，debug了一段时间还是过去了，，有几个需要注意的地方
- dist数组第一维只能开到6，因此dist[i][j]表示为第i个亲戚到车站j的距离
如果第1个亲戚的车站是2，2车站到1车站的距离是8，那么dist[1][1]=8,而不是dist[2][1]=8
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N=1001000;
int n,m;
int a[10];
int e[N],ne[N],h[N],w[N],idx,st[N],dist[6][500010];
typedef pair<int,int> pii;
int ans=0x3f3f3f3f;
void add(int a,int b,int c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
void djk(int s)
{
priority_queue<pii,vector<pii>,greater<pii>> heap;
memset(st,0,sizeof st);
dist[s][a[s]]=0;
heap.push({0,a[s]});
while(heap.size())
{
auto t=heap.top();
heap.pop();
int u=t.second;
int d=t.first;
if(st[u]) continue;
st[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[s][j]>dist[s][u]+w[i])
{
dist[s][j]=dist[s][u]+w[i];
heap.push({dist[s][j],j});
}
}
}
}
//目前在第u个车站，已经拜访了k个车站
void dfs(int u,int k,int dis)
{
//cout<<u<<" "<<k<<" "<<dis<<endl;
if(dis>=ans) return;
if(k==5)
{
ans=dis;
return;
}
for(int i=1;i<=5;i++)
{
if(st[a[i]]) continue;
st[a[i]]=1;
dfs(i,k+1,dis+dist[u][a[i]]);
st[a[i]]=0;
}
}
int main()
{
memset(h,-1,sizeof h);
memset(dist,0x3f,sizeof dist);
cin>>n>>m;
a[0]=1;
for(int i=1;i<=5;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
for(int i=0;i<=5;i++)
{
djk(i);
}
memset(st,0,sizeof st);
dfs(0,0,0);
//cout<<dist[1][4]<<endl;
cout<<ans;
return 0;
}
2023/12/21
第一遍超时了，原因在于每次dfs都要算一次djk。
没有想到djk可以先算好，就5个邻居，算5次就行，保留从当前邻居到其他所有点的最短路径
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N=1000010;
typedef pair<int, int> PII;
int e[N], ne[N], w[N], h[N], idx;
int st[N];
int dist[7][N];
int n,m;
int qq[10];
// 最短时间
int result = 0x3f3f3f3f;
// 当前亲戚是否被访问过
int sq[10];
void add(int a,int b,int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
// 做以第s个邻居为起点的djk
void djk(int s)
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
memset(st, 0, sizeof(st));
int start = qq[s];
dist[s][start] = 0;
heap.push({0, start});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int d = t.first;
int v = t.second;
if(st[v]) continue;
st[v] = 1;
for(int i=h[v];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[s][j] > dist[s][v] + w[i])
{
dist[s][j] = dist[s][v] + w[i];
heap.push({dist[s][j], j});
}
}
}
}
// 当前访问了cnt个亲戚，花费了cost时间, 上一个访问的亲戚在第s处
void dfs(int cnt, int cost, int s)
{
if(cost >= result) return;
if(cnt == 5)
{
result = min(result, cost);
return;
}
for(int i=1;i<=5;i++)
{
// 如果第i个亲戚已经访问过
if(sq[i]) continue;
// 访问第i个亲戚
sq[i] = 1;
int costi = dist[s][qq[i]];
dfs(cnt+1, cost + costi, i);
sq[i] = 0;
}
}
int main()
{
memset(h, -1, sizeof(h));
memset(dist, 0x3f, sizeof(dist));
cin>>n>>m;
// 第0个邻居是自己
qq[0] = 1;
for(int i=1;i<=5;i++)
{
cin>>qq[i];
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
// 这里从0开始遍历，因为也要算从起点到所有点的最短路
for(int i=0;i<=5;i++)
{
djk(i);
}
dfs(0, 0, 0);
cout<<result;
return 0;
}
