首页 > ACM题库 > HDU-杭电 > HDU 3768-Shopping-最短路径-[解题报告]HOJ
2015
04-10

HDU 3768-Shopping-最短路径-[解题报告]HOJ

Shopping

问题描述 :

You have just moved into a new apartment and have a long list of items you need to buy. Unfortunately, to buy this many items requires going to many different stores. You would like to minimize the amount of driving necessary to buy all the items you need.

Your city is organized as a set of intersections connected by roads. Your house and every store is located at some intersection. Your task is to find the shortest route that begins at your house, visits all the stores that you need to shop at, and returns to your house.

输入:

The first line of input contains a single integer, the number of test cases to follow. Each test case begins with a line containing two integers N and M, the number of intersections and roads in the city, respectively. Each of these integers is between 1 and 100000, inclusive. The intersections are numbered from 0 to N-1. Your house is at the intersection numbered 0. M lines follow, each containing three integers X, Y, and D, indicating that the intersections X and Y are connected by a bidirectional road of length D. The following line contains a single integer S, the number of stores you need to visit, which is between 1 and ten, inclusive. The subsequent S lines each contain one integer indicating the intersection at which each store is located. It is possible to reach all of the stores from your house.

输出:

The first line of input contains a single integer, the number of test cases to follow. Each test case begins with a line containing two integers N and M, the number of intersections and roads in the city, respectively. Each of these integers is between 1 and 100000, inclusive. The intersections are numbered from 0 to N-1. Your house is at the intersection numbered 0. M lines follow, each containing three integers X, Y, and D, indicating that the intersections X and Y are connected by a bidirectional road of length D. The following line contains a single integer S, the number of stores you need to visit, which is between 1 and ten, inclusive. The subsequent S lines each contain one integer indicating the intersection at which each store is located. It is possible to reach all of the stores from your house.

样例输入:

1
4 6
0 1 1
1 2 1
2 3 1
3 0 1
0 2 5
1 3 5
3
1
2
3

样例输出:

4
解题思路:给你一个无向图,求从0号点开始遍历所有的指定点再回到0号点的最短路径,指定点只有10个,所以先spfa然后dfs即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define Inf 999999999
using namespace std;
int head1[100005],head2[15],k,dis[15][100005];
bool vis[15];
struct
{
    int e;
    int w;
    int next;
}edge1[200005],edge2[205];
void add1(int s,int e,int w)
{
    edge1[k].e=e;
    edge1[k].w=w;
    edge1[k].next=head1[s];
    head1[s]=k++;
}
void add2(int s,int e,int w)
{
    edge2[k].e=e;
    edge2[k].w=w;
    edge2[k].next=head2[s];
    head2[s]=k++;
}
void spfa(int s,int n,int *dis)
{
    int i,st,ed;
    bool visit[100005];
    queue<int> x;
    memset(visit,false,sizeof(visit));
    for(i=0;i<n;i++)
        dis[i]=Inf;
    dis[s]=0;
    x.push(s);
    while(!x.empty())
    {
        st=x.front();
        x.pop();
        visit[st]=false;
        for(i=head1[st];i!=-1;i=edge1[i].next)
        {
            ed=edge1[i].e;
            if(dis[ed]>dis[st]+edge1[i].w)
            {
                dis[ed]=dis[st]+edge1[i].w;
                if(!visit[ed])
                {
                    visit[ed]=true;
                    x.push(ed);
                }
            }
        }
    }
}
int dfs(int pos,int len,int n,int c)
{
    int i,ans=Inf;
    vis[pos]=true;
    if(pos==0)
    {
        if(c==n)
            return len;
        else
            return Inf;
    }
    for(i=head2[pos];i!=-1;i=edge2[i].next)
    {
        int ed=edge2[i].e;
        if(!vis[ed]||ed==0)
            ans=min(ans,dfs(ed,len+edge2[i].w,n,c+1));
    }
    vis[pos]=false;
    return ans;
}
int main()
{
    int i,j,m,n,a,b,c,t,p[15],q,cnt,ans;
    scanf("%d",&t);
    while(t--)
    {
        k=cnt=0;ans=Inf;
        memset(head1,-1,sizeof(head1));
        memset(head2,-1,sizeof(head2));
        scanf("%d%d",&n,&m);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add1(a,b,c);
            add1(b,a,c);
        }
        scanf("%d",&q);
        p[cnt]=0;
        spfa(0,n,dis[cnt]);
        cnt++;
        while(q--)
        {
            scanf("%d",&p[cnt]);
            spfa(p[cnt],n,dis[cnt]);
            cnt++;
        }
        k=0;
        for(i=0;i<cnt;i++)
            for(j=0;j<cnt;j++)
                if(i!=j)
                    add2(i,j,dis[i][p[j]]);
        for(i=1;i<cnt;i++)
        {
            memset(vis,false,sizeof(vis));
            vis[0]=true;
            ans=min(ans,dfs(i,dis[0][p[i]],cnt,1));
        }
        printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/hqu_fritz/article/details/39474493


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  4. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  5. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  6. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  7. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。