首页 > 代码库 > 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 最短路