紫书 习题 11-7 UVa 10801 (单源最短路变形)

把每个电梯口看作一个节点， 然后计算边的权值的时候处理一下， 就ok了。

#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 112;
struct Edge { int v, id; };
struct node
{
	int t, v, id;
	bool operator < (const node& rhs) const
	{
		return t > rhs.t;
	}
};	 
vector<Edge> g[MAXN];
vector<int> a;
int d[MAXN], speed[10], n, k, x;

void solve()
{
	priority_queue<node> q;
	REP(i, 0, MAXN) d[i] = (i == 0 ? 0 : 1e9);
	q.push(node{0, 0, -1});
	
	while(!q.empty())
	{
		node x = q.top(); q.pop();
		int u = x.v;
		if(x.t != d[u]) continue;
		
		REP(i, 0, g[u].size())
		{
			int v = g[u][i].v, id = g[u][i].id;
			int w = speed[id] * abs(u - v);
			if(x.id != id && x.id != -1) w += 60;

			if(d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				q.push(node{d[v], v, id});
			}
		}
	} 
	
	if(d[k] == 1e9) puts("IMPOSSIBLE");
	else printf("%d
", d[k]);
}

int main()
{
	while(~scanf("%d%d", &n, &k))
	{
		REP(i, 0, MAXN) g[i].clear();
		REP(i, 0, n) scanf("%d", &speed[i]);
		
		REP(i, 0, n)
		{
			a.clear();
			scanf("%d", &x);
			a.push_back(x);
			
			while(getchar() != '
')
			{
				scanf("%d", &x);
				a.push_back(x);
			}
			
			REP(r, 0, a.size())
				REP(j, r + 1, a.size()) 
				{
					g[a[j]].push_back(Edge{a[r], i});
					g[a[r]].push_back(Edge{a[j], i});
				}
		}
		
		solve();
	}
	
	return 0;	
}