题目链接：

http://acm.hust.edu.cn/vjudge/problem/48416

Shopping Malls

Time Limit: 3000MS
#### 问题描述
> We want to create a smartphone application to help visitors of a shopping mall and you have to calculate
> the shortest path between pairs of locations in the mall. Given the current location of the visitor and his
> destination, the application will show the shortest walking path (in meters) to arrive to the destination.
> The mall has N places in several floors connected by walking paths, lifts, stairs and escalators
> (automated stairs). Note that the shortest path in meters may involve using an escalator in the
> opposite direction. We only want to count the distance that the visitor has walked so each type of
> movement between places has a different cost in meters:
> • If walking or taking the stairs the distance is the euclidean distance between the points.
> • Using the lift has a cost of 1 meter because once we enter the lift we do not walk at all. One
> lift can only connect 2 points. An actual lift connects the same point of different floors, in the
> map all the points connected by a lift have the corresponding edge. So you do not need to worry
> about that. For instance, if there are three floors and one lift at position (1,2) of each floor, the
> input contains the edges (0, 1, 2) → (1, 1, 2), (1, 1, 2) → (2, 1, 2) and (0, 1, 2) → (2, 1, 2). In some
> maps it can be possible that a lift does not connect all the floors, then some of the edges will not
> be in the input.
> • The escalator has two uses:
> – Moving from A to B (proper direction) the cost is 1 meter because we only walk a few steps
> and then the escalator moves us.
> – Moving from B to A (opposite direction) has a cost of the euclidean distance between B and
> A multiplied by a factor of 3.
> The shortest walking path must use only these connections. All the places are connected to each
> other by at least one path.
#### 输入
> The input file contains several data sets, each of them as described below. Consecutive
> data sets are separated by a single blank line.
> Each data set contains the map of a unique shopping mall and a list of queries.
> The first line contains two integers N (N ≤ 200) and M (N −1 ≤ M ≤ 1000), the number of places
> and connections respectively. The places are numbered from 0 to N −1. The next N lines contain floor
> and the coordinates x, y of the places, one place per line. The distance between floors is 5 meters. The
> other two coordinates x and y are expressed in meters.
> The next M lines contain the direct connections between places. Each connection is defined by the
> identifier of both places and the type of movement (one of the following: ‘walking’, ‘stairs’, ‘lift’,
> or ‘escalator’). Check the cost of each type in the description above. The type for places in the same
> floor is walking.
> The next line contains an integer Q (1 ≤ Q ≤ 1000) that represents the number of queries that
> follow. The next Q lines contain two places each a and b. We want the shortest walking path distance
> to go from a to b.
#### 输出
> For each data set in the input the output must follow the description below. The outputs
> of two consecutive data sets will be separated by a blank line.
> For each query write a line with the shortest path in walked meters from the origin to the destination,
> with each place separated by a space.

样例

sample input

6 7

3 2 3

3 5 3

2 2 3

2 6 4

1 1 3

1 4 2

0 1 walking

0 2 lift

1 2 stairs

2 3 walking

3 4 escalator

5 3 escalator

4 5 walking

5

0 1

1 2

3 5

5 3

5 1

sample output

0 1

1 0 2

3 4 5

5 3

5 3 2 0 1

题解

floyd最短路+路径记录。注意重边和输出格式

代码

#include<map>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

using namespace std;

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const int maxn=222;

struct Point{

	double x,y,z;

}pt[maxn];

double mat[maxn][maxn];

int pre[maxn][maxn];

int n,m; 

double dis(const Point& p1,const Point& p2){

	return sqrt(25*(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));

}

void init(){

	rep(i,0,n+1) rep(j,0,n+1){

		mat[i][j]=INF*1.0;

		if(i==j) mat[i][j]=0;

		pre[i][j]=i;

	}

}

int main(){

	int kase=0;

	while(scanf("%d%d",&n,&m)==2&&n){

		init();

		if(kase++) puts("");

		rep(i,0,n) scanf("%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z);

		while(m--){

			int u,v; char str[22];

			scanf("%d%d%s",&u,&v,str);

			double val;

			if(str[0]=='w'||str[0]=='s'){

				mat[u][v]=min(mat[u][v],dis(pt[u],pt[v]));

				mat[v][u]=min(mat[v][u],dis(pt[v],pt[u]));

			}else if(str[0]=='e'){

				mat[u][v]=min(mat[u][v],1.0);

				mat[v][u]=min(mat[v][u],3*dis(pt[u],pt[v]));

			}else{

				mat[u][v]=min(mat[u][v],1.0);

				mat[v][u]=min(mat[v][u],1.0);

			}

		}

		rep(k,0,n) rep(i,0,n) rep(j,0,n){

			if(mat[i][j]>mat[i][k]+mat[k][j]){

				mat[i][j]=mat[i][k]+mat[k][j];

				pre[i][j]=pre[k][j];

			}

		}

		int q;

		scanf("%d",&q);

		while(q--){

			int u,v;

			scanf("%d%d",&u,&v);

			VI path;

			path.pb(v);

			while(pre[u][v]!=u){

//				bug(v);

				path.pb(pre[u][v]);

				v=pre[u][v];

			}

			path.pb(u);

			reverse(all(path));

			rep(i,0,path.size()-1) printf("%d ",path[i]);

			printf("%d\n",path[path.size()-1]);

		}

	}

	return 0;

}