题意:
有n<6部电梯,给出每部电梯可以停的一些特定的楼层,要求从0层到达第k层出来,每次换乘需要60秒,每部电梯经过每层所耗时不同,具体按 层数*电梯速度 来算。问经过多少秒到达k层(k可以为0)?
思路:
dijkstra再加一些特殊的处理就行了。首先要考虑,如何建图:
(1)每层作为一个点。但是特定路径可以有多种权,比如从2->5可以坐1号电梯10s,但是坐2号只需要5s,所以有重边。
(2)k=0时,不耗时间。
(3)有多种路径可达同一楼层且权值相同,那么从本楼层到另一楼层有多种选择,有时可以不换电梯,有时需要换。比如到达5楼的有2条路径,权都是5,但是是两部不同的电梯1和2,此时有其他电梯可以从5到7楼,其中有一部仍是电梯1,如果坐电梯1则不需要换乘时间,坐其他电梯就要了。所以要记录到某个点权值相等的电梯号。
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=;
int take[];
char s[];
vector<int> lift[], vect[];
int cost[N], vis[N];
struct node
{
int from, to, lift, cost;
node(){};
node(int from,int to,int lift,int cost):from(from),to(to),lift(lift),cost(cost){};
}edge[];
int edge_cnt; void add_node(int from,int to,int lift,int cost)
{
edge[edge_cnt]=node(from,to,lift,cost);
vect[from].push_back(edge_cnt++);
} void build_graph(int n) //重新建图
{
for(int i=; i<n; i++)
{
for(int j=; j<lift[i].size(); j++)
{
for(int t=j+; t<lift[i].size(); t++)
{
int a=lift[i][j];
int b=lift[i][t];
add_node(a,b,i,(b-a)*take[i]);
add_node(b,a,i,(b-a)*take[i]);
}
}
}
} int dijkstra(int s,int e)
{
vector<int> flo[];
memset(cost,0x7f,sizeof(cost));
memset(vis,,sizeof(vis) ); priority_queue<pii,vector<pii>,greater<pii> > que;
que.push( make_pair(,s));
cost[s]=;
while(!que.empty())
{
int x=que.top().second;que.pop();
if(vis[x]) continue; vis[x]=;
for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
int ext=; for(int j=; j<flo[e.from].size(); j++) //如果有一个匹配,就不用额外时间
if( flo[e.from][j]==e.lift ) ext=; if(cost[e.to]>=cost[e.from]+ext+e.cost )
{
if( cost[e.to]>cost[e.from]+ext+e.cost ) flo[e.to].clear();
flo[e.to].push_back(e.lift); cost[e.to]= cost[e.from] +ext +e.cost;
que.push( make_pair(cost[e.to], e.to) );
}
}
}
return cost[e];
} int main()
{
freopen("input.txt", "r", stdin);
int n, k;
while(~scanf("%d%d",&n,&k))
{
for(int i=; i<n; i++) lift[i].clear();
for(int i=; i<; i++) vect[i].clear();
memset(s,,sizeof(s)); for(int i=; i<n; i++) scanf("%d",&take[i]);
getchar();
for(int i=; i<n; i++)
{
lift[i].clear();
gets(s);
int p=;
while(s[p]!='\0')
{
if(s[p]==' ') p++;
int tmp=;
while(s[p]!=' ' &&s[p]!='\0' ) tmp=tmp*+(s[p++]-'');
lift[i].push_back(tmp);
}
}
build_graph(n);
int ans=dijkstra(,k);
if(!k) puts("");
else if(ans==INF) puts("IMPOSSIBLE");
else printf("%d\n", ans- ) ;
}
return ;
}
AC代码