Hotel booking时间限制(普通/Java) : 4000 MS/ 10000 MS 运行内存限制 : 65536 KByte
总提交 : 1 测试通过 : 1 描述
A transport company often needs to deliver goods from one city to another city. The transport company has made a special deal with a hotel chain which allows its drivers to stay in the hotels of this chain for free. 输入
The input file contains several test cases. Each test case starts with a line containing an integer n, 输出
For each test case, print one line containing the minimum number of hotels the transport company has to book for a delivery from city 1 to city n. 样例输入 6 样例输出 2 提示
题目来源 University of Ulm |
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1454
二维spfa，优先队列优化。 （其实我就是当作BFS来做，只不过做法类似spfa）
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct Edge{
int nx,cost,v;
}edge[210000];
int ef[10010],tol=0;
void add_edge(int a,int b,int cost){
edge[tol].v=b;
edge[tol].cost=cost;
edge[tol].nx=ef[a];
ef[a]=tol++;
}
struct Node{
int u,minute,vis;
Node(){};
Node(int uu,int mm,int vv){
u=uu; // 当前所在位置
minute=mm; // 记录从旅馆/起点出发，到达u位置所花费的最时间
vis=vv; // 记录入住次数
}
bool friend operator<(Node a,Node b){ // 优先级为： 访问旅馆次数较少的点先走，次数相同则以花费时间少的点先走
return a.vis!=b.vis?a.vis>b.vis:a.minute>b.minute;
}
};
priority_queue<Node>que;
int n;
int has[10010];
int Time[10010]; // Time[v]记录【v位置】与 【起点/最近的旅馆】 的最短距离
int Count[10010]; // Count记录当前已入住的次数
int spfa(){
int k,v,tmp;
Node now,nx;
que.push(Node(1,0,0));
while(!que.empty()){
now=que.top();
que.pop();
if(now.u==n) return now.vis;
for(k=ef[now.u];k!=-1;k=edge[k].nx){
v=edge[k].v;
if(Count[v]<now.vis){ // 当访问旅馆次数增加，那么之前记录的时间作废
Count[v]=now.vis;
Time[v]=601; // 重新记录时间为601分钟
}
tmp=now.minute+edge[k].cost; // 从【起点/旅馆】出发，到达v时所花费的时间
if(tmp>=Time[v] || has[v]==-1) continue; // 时间比记录的Time[v]还高，那么不再访问
Time[v]=tmp;
que.push(Node(v,tmp,now.vis));
if(has[v]==1){ // 一开始写在continue那句之前，样例都没过，囧
has[v]=-1; // 标记住过的旅馆不再住，（为何？既然之前更优的走法先入住了，现在更搓的走法何必再入住。可以仔细想哈）
que.push(Node(v,0,now.vis+1));
}
}
}
return -1;
}
void INIT(){
int i;
for(i=1;i<=n;i++){
has[i]=0;
ef[i]=Count[i]=-1;
}
tol=0;
while(!que.empty()) que.pop();
}
int main(){
int m,a,b,len;
while(~scanf("%d",&n)){
if(!n) break;
INIT();
scanf("%d",&m);
while(m--){
scanf("%d",&a);
has[a]=1;
}
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&a,&b,&len);
add_edge(a,b,len);
add_edge(b,a,len);
}
printf("%d\n",spfa());
}
return 0;
}