首页 > ACM题库 > HDU-杭电 > HDU 3120-Dolphin-最短路径-[解题报告]HOJ
2014
03-02

HDU 3120-Dolphin-最短路径-[解题报告]HOJ

Dolphin

问题描述 :

Dolphins are marine mammals that are closely related to whales and porpoises. They might have some kind of the biggest brains in the water, but are dolphins really smart? Some scientists say that they use their big brains to stay warm in the sea, rather than for lots of thinking. Obviously those scientists don’t think dolphins are smart.
We know that the brain is made up of two types of cells � neurons and glia. Neurons do the thinking, while glia do things like keeping the brain warm to help the neurons. After looking at how dolphins’ brains are put together, they claim that dolphins have lots of glia and not many neurons.
In order to find out how smart the dolphins are, we throw one of them into a maze we’ve just created, to see how long it’ll take the dolphin to get out.
The maze consists of nodes and bidirectional edges connecting them.
The dolphin needs power to swim, so we place exactly one fish at each node for him to enjoy.
The dolphin is not interested in eating the same kind of fish more than once, but he can’t resist any food if it’s just in front to him! As a result, the dolphin decided to PLAN a route before going, so that it will not REACH any kind of fish more than once.
Given the information above, can you tell me the minimum time that the dolphin needs to get out?

输入:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of four integers N, M, S and E, indicating the number of nodes, the number of edges, the starting node and destination.
Each of the next M lines consists of three integers U, V, C, indicating that there is an edge with length C between node U and V. It will take a dolphin C time to pass this edge.
The next line consists of N integers. Ki indicates the label of which kind fishes i-th node has.

输出:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of four integers N, M, S and E, indicating the number of nodes, the number of edges, the starting node and destination.
Each of the next M lines consists of three integers U, V, C, indicating that there is an edge with length C between node U and V. It will take a dolphin C time to pass this edge.
The next line consists of N integers. Ki indicates the label of which kind fishes i-th node has.

样例输入:

2
2 1 0 1
0 1 1
0 0
4 4 0 3
0 1 1
1 3 1
0 2 2
2 3 2
0 0 1 2

样例输出:

-1
4

这个题很不错哦,用到了最短路+二分答案+dfs,出题人太厉害了

首先,100个点,总共的点的标号数目可能达到100,压缩不了,那就只能dfs了,但肯定需要剪枝

我自己想到的剪枝就是,先不管标号的问题,从终点做一次最短路,记录路径,如果源点不可达,则无解,如果这条路径上的点刚好标号都不一样,则输出到源点的最短路径

然后就暴力dfs,如果当前长度加上不考虑标号时当前点到终点的最短路径都大于当前最优解,就返回,这样还是T了

后来想能否快速找到一个可行解作为上限值,但不会找,查了解题报告才知道,可以二分答案,相当于有目的地找多次可行解,然后去验证,很巧妙

这题最让我觉得不可思议的就是每次dfs到一个点的时候都去求一次该点到终点的最短路,用来剪枝,好神奇啊

还有一个值得注意的地方就是,dfs的时候,在进入某个点之前把它标记,然后dfs回来时再撤销标记,否则,在进入某个点后标记,退出这个点时在撤销,可能会由于剪枝而忘记撤销标记的情况

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=1005;
const int inf=1<<26;
struct node 
{
    int v,w,next;
}g[MAX*100];
int adj[MAX],e,vis1[MAX],vis2[MAX],kind[MAX],n,m;
int dis[MAX],fa[MAX],pre[MAX];
int flag[MAX];
bool pos[MAX],found;
void add(int u,int v,int w)
{
    g[e].v=v; g[e].w=w; g[e].next=adj[u]; adj[u]=e++;
}
void spfa(int s,int t,int k)
{
    int i,u,v;
    queue<int>que;
    for(i=0;i<=n;i++)
        dis[i]=inf;
    if(k)
    	memset(pre,-1,sizeof(pre));
    dis[s]=0;
    memset(vis1,0,sizeof(vis1));
    vis1[s]=1;
    que.push(s);
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        vis1[u]=0;
        for(i=adj[u];i!=-1;i=g[i].next)
        {
            v=g[i].v;
            if(vis2[kind[v]])
                continue;
            //if(kind[v]==kind[t])
                //continue;
            //if(kind[v]==kind[s]&&v!=s)
                //continue;
            if(dis[v]>dis[u]+g[i].w)
            {
                dis[v]=dis[u]+g[i].w;
                pre[v]=u;
                if(!vis1[v])
                {
                    vis1[v]=1;
                    que.push(v);
                }
            }
        }
    }
}                
bool check()
{
    for(int i=0;i<MAX;i++)
        if(flag[i]>1)
            return false;
    return true;
}
bool dfs(int u,int now,int limit,int t)
{
    if(now>limit)
        return false;
    if(u==t)
        return true;
    spfa(u,t,0);
    if(now+dis[t]>limit)
        return false;
    int i,v;
    for(i=adj[u];i!=-1;i=g[i].next)
    {
        v=g[i].v;
        if(vis2[kind[v]])
            continue;
        vis2[kind[v]]=1;
        if(dfs(v,now+g[i].w,limit,t))
            return true;
        vis2[kind[v]]=0;
    }
    return false;
}
void solve(int s,int t,int sum)
{
    int l=1,r=sum,ans=-1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        memset(vis2,0,sizeof(vis2));
        vis2[kind[s]]=1;
        if(dfs(s,0,mid,t))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    printf("%d\n",ans);
}
inline int nextInt()
{
	int res = 0; char ch;
	bool neg = false;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') neg = true;
	else res = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - '0';
	if (neg) res = - res;
	return res;
}
int main()
{
    int i,j,k,T,s,t,sum=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);
        memset(adj,-1,sizeof(adj));
        e=0;
        while(m--)
        {
            //scanf("%d%d%d",&i,&j,&k);
            i=nextInt(); j=nextInt(); k=nextInt();
            add(i,j,k); add(j,i,k);
            sum+=k;
        }
        for(i=0;i<n;i++)
        {
            //scanf("%d",&kind[i]);
            kind[i]=nextInt();
        }
        if(s==t)
        {
            puts("0");
            continue;
        }
        memset(vis2,0,sizeof(vis2));
        vis2[kind[t]]=1;
        spfa(t,s,1);
        memset(flag,0,sizeof(flag));
        if(pre[s]==-1)
        {
            puts("-1");
            continue;
        }
        for(i=s;i!=-1;i=pre[i])
        {
            flag[kind[i]]++;
        }
        if(check())
        {
            printf("%d\n",dis[s]);
            continue;
        }
        solve(s,t,sum);
    }
    return 0;
}

参考:http://blog.csdn.net/scorpiocj/article/details/6761916