题目描述
重庆城里有 nn 个车站，mm 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 11，他有五个亲戚，分别住在车站 a,b,c,d,ea,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？
输入格式
第一行：n,mn,m，分别为车站数目和公路的数目。
第二行：a,b,c,d,ea,b,c,d,e，分别为五个亲戚所在车站编号。
以下 mm 行，每行三个整数 x,y,tx,y,t，为公路连接的两个车站编号和时间。
输出格式
仅一行，包含一个整数 TT，为最少的总时间。保证 T\le 10^9T≤109。
输入输出样例
输入 #1复制
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
输出 #1复制
21
先求出 从1以及5个亲戚家出发,到所有点的最短路,然后暴力枚举这五个点的摆放顺序,求最小值.比如当1 -> 3 ->2 ->4 ->5 ->6时,结果应是1到3的最短路+3到2的最短路+......,然后取所有情况里面的最小值.写的时候类似求全排列的函数,可以写一个dfs
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX_N = 50007;
const int INF = 1e9 + 7;
typedef pair<int, int> P;
int N, M;
struct node{
int v;
int d[MAX_N];
};
node re[7];
struct edge{
int from, to, cost;
};
vector<edge> G[MAX_N];
void dijkstra(int s,int d[]){
for (int i = 1; i <= N; i++){
d[i] = INF;
}
d[s] = 0;
priority_queue <P, vector<P>, greater<P>> que;
que.push(P(0,s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(d[v]<p.first){
continue;
}
for (int i = 0;i < G[v].size(); i++){
edge e = G[v][i];
if(d[e.to]>d[e.from]+e.cost){
d[e.to] = d[e.from] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
int ans = INF;
bool book[7];
void dfs(int cnt,vector<int> & vec){
if(cnt == 6){
int t = re[1].d[re[vec[0]].v];
for (int i = 1;i<vec.size(); i++){
t += re[vec[i - 1] ].d[re[vec[i]].v];
}
ans = min(t, ans);
}else{
for (int i = 2; i <= 6; i++){
if(!book[i]){
vec.push_back(i);
book[i] = true;
int c = cnt + 1;
dfs(c, vec);
vec.pop_back();
book[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin >> N >> M;
re[1] .v = 1;
for (int i = 2; i <= 6; i++){
cin >> re[i].v;
}
for (int i = 1; i <= M; i++){
edge e;
cin >> e.from >> e.to >> e.cost;
G[e.from].push_back(e);
swap(e.from, e.to);
G[e.from].push_back(e);
}
for(int i = 1; i <= 6; i++){
dijkstra(re[i].v,re[i].d);
}
vector<int> v;
dfs(1, v);
cout << ans << endl;
return 0;
}
正边图一定要用dijkstra......这个题会卡spfa......以下是TLE的代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX_N = 50007;
const int INF = 1e9 + 7;
int vis[MAX_N];
int N, M;
struct node{
int v;
int d[MAX_N];
};
node re[7];
struct edge{
int from, to, cost;
};
vector<edge> G[MAX_N];
void spfa(int s,int d[]){
for (int i = 1; i <= N; i++){
d[i] = INF;
vis[i] = false;
}
d[s] = 0;
queue<int> que;
que.push(s);
vis[s] = true;
while(!que.empty()){
int v = que.front();
que.pop();
vis[v] = false;
for (int i = 0;i<G[v].size(); i++){
edge e = G[v][i];
if(d[e.to]>d[e.from]+e.cost){
d[e.to] = d[e.from] + e.cost;
if(!vis[e.to]){
vis[e.to] = true;
que.push(e.to);
}
}
}
}
}
int ans = INF;
bool book[7];
void dfs(int cnt,vector<int> & vec){
if(cnt == 6){
int t = re[1].d[re[vec[0]].v];
for (int i = 1;i<vec.size(); i++){
t += re[vec[i - 1] ].d[re[vec[i]].v];
}
ans = min(t, ans);
}else{
for (int i = 2; i <= 6; i++){
if(!book[i]){
vec.push_back(i);
book[i] = true;
int c = cnt + 1;
dfs(c, vec);
vec.pop_back();
book[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin >> N >> M;
re[1] .v = 1;
for (int i = 2; i <= 6; i++){
cin >> re[i].v;
}
for (int i = 1; i <= M; i++){
edge e;
cin >> e.from >> e.to >> e.cost;
G[e.from].push_back(e);
swap(e.from, e.to);
G[e.from].push_back(e);
}
for(int i = 1; i <= 6; i++){
spfa(re[i].v,re[i].d);
}
vector<int> v;
dfs(1, v);
cout << ans << endl;
return 0;
}
