hdu 2992 Hotel booking(spfa+floyd+地图)

hdu 2992 Hotel booking(spfa+floyd+map)

http://acm.hdu.edu.cn/showproblem.php?pid=2992

题意：运输公司要从初始城市运送货物到目的城市，共有n个城市，编号是1~n。出发点和目的地分别是1和n号城市。在这些城市中有h个免费客栈，司机一天最多能走10小时，晚上选择一个客栈休息。给出h个客栈所在的城市以及m个城市的连接情况，问最少需要的客栈数。

思路：把h个客栈看做点，编号为1~h,起点标号为0，终点标号为h+1,这样共h+2个点。spfa求任两个客栈之间的路程，若 <= 600,则建边（注意建边建的是客栈的编号，而不是城市编号，用map映射），权值为1。最后求0到h+1的最短路。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

struct node
{
    int u,v;
    int w;
};

map <int, int> mp;
vector <struct node> edge[10010];

int n,m,num;
int a[110];
int graph[110][110]; //映射后的图

void init()
{
    mp.clear();
    for(int i = 1; i <= n; i++)
        edge[i].clear();

    for(int i = 0; i <= num+2; i++)
    {
        for(int j = 0; j <= num+2; j++)
        {
            if(i == j) graph[i][j] = 0;
            else graph[i][j] = INF;
        }
    }
}

void spfa(int s)
{
    queue <int> que;
    int dis[10100];
	int inque[10100];
	
    while(!que.empty()) que.pop();
    memset(dis,INF,sizeof(dis));
    memset(inque,0,sizeof(inque));

    dis[s] = 0;
    inque[s] = 1;
    que.push(s);

    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        inque[u] = 0;
        for(int i = 0; i < (int)edge[u].size(); i++)
        {
            int v = edge[u][i].v;
            if(dis[v] > dis[u] + edge[u][i].w)
            {
                dis[v] = dis[u] + edge[u][i].w;
                if(!inque[v])
                {
                    inque[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(dis[i] <= 600)
            graph[ mp[s] ][ mp[i] ] = 1;
    }
}

void floyd() //求0到h+1的最短路
{
    for(int k = 0; k <= num+1; k++)
    {
        for(int i = 0; i <= num+1; i++)
        {
            for(int j = 0; j <= num+1; j++)
            {
                if( graph[i][k] + graph[k][j] < graph[i][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }
}

int main()
{
    while(~scanf("%d",&n) && n)
    {
        scanf("%d",&num);
        init();
        for(int i = 1; i <= num; i++)
        {
            scanf("%d",&a[i]);
            mp[ a[i] ] = i;
        }
        
        mp[1] = 0;
        mp[n] = num+1;
        a[0] = 1;
        a[num+1] = n;

        scanf("%d",&m);
        while(m--)
        {
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            edge[u].push_back((struct node) {u,v,w});
            edge[v].push_back((struct node) {v,u,w});
        }

        for(int i = 0; i <= num+1; i++)
            spfa( a[i] );

        floyd();

        if(graph[0][num+1] < INF)
            printf("%d\n",graph[0][num+1]-1);
        else printf("-1\n");
    }
    return 0;
}