首页 > 代码库 > UVA 10801 Lift Hopping 最短路
UVA 10801 Lift Hopping 最短路
2种方式直接代码就可以了。注意首次不需要60S的转换
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 105const int INF = 0x3f3f3f3f;int T[10],N,K;int w[MAXN][MAXN],d[MAXN];int src[MAXN];typedef pair<int,int> pii;priority_queue<pii,vector<pii>,greater<pii> > q;void read(){ memset(w,0x3f,sizeof(w)); for (int i = 0; i < N; i++) scanf("%d",&T[i]); for (int i = 0; i < N; i++) { int cas = 0; char ch; do { scanf("%d",&src[cas++]); ch = getchar(); }while (ch != ‘\n‘); for (int j = 0; j < cas; j++) for (int k = j; k < cas; k++) { w[src[j]][src[k]] = min(w[src[j]][src[k]],abs(src[k] - src[j]) * T[i]); w[src[k]][src[j]] = min(w[src[k]][src[j]],abs(src[k] - src[j]) * T[i]); } }}void SPFA(){ bool inq[MAXN]; memset(inq,false,sizeof(inq)); memset(d,0x3f,sizeof(d)); d[0] = 0; queue<int>que; while (!que.empty()) que.pop(); que.push(0); while (!que.empty()) { int u = que.front();que.pop(); inq[u] = false; for (int i = 0; i < MAXN; i++) { if (u == 0) { if (d[i] > d[u] + w[u][i]) { d[i] = d[u] + w[u][i]; if (!inq[i]) { inq[i] = true; que.push(i); } } } else { if (d[i] > d[u] + w[u][i] + 60) { d[i] = d[u] + w[u][i] + 60; if (!inq[i]) { inq[i] = true; que.push(i); } } } } }}void dijkstra(){ memset(d,0x3f,sizeof(d)); d[0] = 0; q.push(make_pair(d[0],0)); while (!q.empty()) { pii t = q.top();q.pop(); int u = t.second; if (t.first != d[u]) continue; for (int v = 0; v < MAXN; v++) { if (u == 0) { if (d[v] > d[u] + w[u][v]) { d[v] = d[u] + w[u][v]; q.push(make_pair(d[v],v)); } } else { if (d[v] > d[u] + w[u][v] + 60) { d[v] = d[u] + w[u][v] + 60; q.push(make_pair(d[v],v)); } } } }}int main(){ //freopen("sample.txt","r",stdin); while (scanf("%d%d",&N,&K) != EOF) { read(); SPFA(); //dijkstra(); if (d[K] == INF) puts("IMPOSSIBLE"); else printf("%d\n",d[K]); } return 0;}
UVA 10801 Lift Hopping 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。