新年おめでとうございます(Dijkstra+サブセット生成)
2908 ワード
【問題の説明】
重慶城にはnつの駅があり、m本の双方向道路がその中のいくつかの駅を接続している.2つの駅ごとに最大1つの道路で直接接続され、どの駅からも1つ以上の道路を通って他の駅に着くことができますが、経路によって時間がかかる可能性があります.1つの経路にかかる時間は、経路上のすべての道路に必要な時間と等しい.
佳佳の家は駅にあります.彼は5人の親戚がいて、それぞれ駅a、b、c、d、eに住んでいます.年を越して、彼は自分の家を出発して、すべての親戚を訪問して(順番は任意です)、彼らに祝日の祝福を送る必要があります.どのように行って、最も少ない時間が必要ですか?
【入力形式】
1行目:n(n<=50000)、m(m<=100000)は、駅数と道路数である.
2行目:a、b、c、d、eは、5人の親戚がいる駅番号(1次にm行は、1行あたり3つの整数x、y、t(1<=x、y<=n、1<=t<=100)で、道路接続の2つの駅番号と時間である.
【出力形式】
1行のみ、整数Tを含む最小の合計時間
【入力サンプル】
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
【データ範囲】
n<=50,000
m<=100,000
分析:
一、最短の問題は、自然に三大アルゴリズムを思いつく.
二、5つの点に起点を加えて全部で6つの点で、1つ目の点は1で、固定されていて、その他の点の順序は任意で、1回の処理が終わりません;しかし、全部で6つの点しかないので、各点に1回の単一ソースの最短ルートが考えられ、それぞれ1つのdist配列で記録されています.そして可能なすべての配列を列挙し、最小の経路を求めればよい.
重慶城にはnつの駅があり、m本の双方向道路がその中のいくつかの駅を接続している.2つの駅ごとに最大1つの道路で直接接続され、どの駅からも1つ以上の道路を通って他の駅に着くことができますが、経路によって時間がかかる可能性があります.1つの経路にかかる時間は、経路上のすべての道路に必要な時間と等しい.
佳佳の家は駅にあります.彼は5人の親戚がいて、それぞれ駅a、b、c、d、eに住んでいます.年を越して、彼は自分の家を出発して、すべての親戚を訪問して(順番は任意です)、彼らに祝日の祝福を送る必要があります.どのように行って、最も少ない時間が必要ですか?
【入力形式】
1行目:n(n<=50000)、m(m<=100000)は、駅数と道路数である.
2行目:a、b、c、d、eは、5人の親戚がいる駅番号(1
【出力形式】
1行のみ、整数Tを含む最小の合計時間
【入力サンプル】
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
【データ範囲】
n<=50,000
m<=100,000
分析:
一、最短の問題は、自然に三大アルゴリズムを思いつく.
二、5つの点に起点を加えて全部で6つの点で、1つ目の点は1で、固定されていて、その他の点の順序は任意で、1回の処理が終わりません;しかし、全部で6つの点しかないので、各点に1回の単一ソースの最短ルートが考えられ、それぞれ1つのdist配列で記録されています.そして可能なすべての配列を列挙し、最小の経路を求めればよい.
#include
#include
#include
using namespace std;
const int maxn=50005;
const int maxm=100005;
const int INF=150000000;
int n,m,np=0,last[maxn],rela[6],dist[6][maxn];
struct edge{int to,w,pre;}E[maxm*2];
struct data
{
int d,id;
friend bool operator < (data a,data b) {return a.d>b.d;}
};
char c;
inline void qkscanf(int &x)
{
for(c=getchar();c'9';c=getchar());
for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
}
inline void addedge(int u,int v,int w)
{
E[++np]=(edge){v,w,last[u]};
last[u]=np;
}
int done[maxn];
inline void Dijkstra(int s,int *dis)
{
priority_queuepq;
for(int i=1;i<=n;i++) dis[i]=INF,done[i]=0;
pq.push((data){0,s});
dis[s]=0;
while(!pq.empty())
{
data t=pq.top();pq.pop();
int i=t.id;
if(done[i]) continue;
done[i]=1;
for(int p=last[i];p;p=E[p].pre)
{
int j=E[p].to,w=E[p].w;
if(dis[j]>dis[i]+w)
{
dis[j]=dis[i]+w;
pq.push((data){dis[j],j});
}
}
}
}
int order[6];
int ans=INF;
inline void check()
{
int cnt=0;
for(int i=0;i<5;i++)
{
int x=order[i],y=rela[order[i+1]];//i i+1
cnt+=dist[x][y];
}
ans=min(ans,cnt);
}
int vis[6];
inline void DFS(int cnt)
{
if(cnt>5)//
{
check();
return;
}
for(int i=1;i<=5;i++)
{
if(!vis[i])
{
vis[i]=1;
order[cnt]=i;// rela ，
DFS(cnt+1);
vis[i]=0;
}
}
}
int main()
{
// freopen("in.txt","r",stdin);
//input
qkscanf(n);qkscanf(m);
for(int i=1;i<=5;i++) qkscanf(rela[i]);
register int u,v,w;
for(int i=1;i<=m;i++)
{
qkscanf(u);qkscanf(v);qkscanf(w);
addedge(u,v,w);addedge(v,u,w);
}
//solve
rela[0]=1;// 1
for(int i=0;i<=5;i++) Dijkstra(rela[i],dist[i]);//
order[0]=0;// ， 1（rela 0）
DFS(1);
printf("%d",ans);
}