hdu 3873 Invade the Mars (有限制条件的最短路。。)

2016-07-14 · 2 min read · dijkstra 最短路

hdu3873题目链接

题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

然后dij写得比较少。。。不是很熟练。。参考了这篇题解参考题解

思路倒是不难想，我在写spfa的时候也是这样想法，然后试图记录路径递归来搞。。。。。然而并不可以2333

也是第一次遇到带限制条件的最短路。。。还是多积累吧。。。

哦对了。。。权值比较大。。。要记得开long long

/* ***********************************************
Author :111qqz
Created Time :2016年07月15日 星期五 00时32分14秒
File Name :code/hdu/3873.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < long long ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=3E3+7;
 7const int M=7E4+7;
 8int n,m;
 9int cnt;
10int head[N];
11int in[N]; //in[i]表示点i被几个点保护。。。
12vector <int>prec[N];
13LL d[N];
14bool vis[N];
15LL maxt[N];
16struct Edge
17{
18    int v;
19    LL w;
20    int nxt;
21}edge[M];

 1void init()
 2{
 3    ms(head,-1);
 4    ms(in,0);
 5    cnt = 0 ;
 6    for ( int i = 1 ; i <= n ; i++) prec[i].clear();
 7}
 8void addedge( int u,int v,int w)
 9{
10    edge[cnt].v = v;
11    edge[cnt].w = w;
12    edge[cnt].nxt = head[u];
13    head[u]=cnt;
14    cnt++;
15}

1LL dij( int s)
2{
3    priority_queue<pi,vector<pi>,greater<pi> >q;
4    ms(d,0x3f);
5    ms(vis,false);
6    ms(maxt,0);

    d[s] = 0 ;
    q.push(make_pair(d[s],s));

1    while (!q.empty())
2    {
3	pi cur = q.top();
4	q.pop();
5	int u = cur.sec;
6	if (vis[u]) continue;
7	vis[u] = true;

 1	int siz = prec[u].size();
 2	for ( int i = 0 ; i < siz ; i++)
 3	{
 4	    int v = prec[u][i];
 5	    in[v]--;
 6	    maxt[v] = max(maxt[v],d[u]);
 7	    if (d[v]!=inf&&!in[v])
 8	    {
 9		d[v] = max(d[v],maxt[v]);
10		q.push(make_pair(d[v],v));
11	    }

 1	}
 2	for  ( int i = head[u] ; i != -1 ; i = edge[i].nxt)
 3	{
 4	    int v = edge[i].v;
 5	    LL w = edge[i].w;
 6	    if (d[v]>d[u]+w)
 7	    {
 8		d[v] = d[u] + w;
 9		if (!in[v]) q.push(make_pair(d[v],v));
10	    }
11	}
12    }
13    return d[n];

1}
2int main()
3{
4	#ifndef  ONLINE_JUDGE 
5	freopen("code/in.txt","r",stdin);
6  #endif

1	int T;
2	cin>>T;
3	while (T--)
4	{
5	    scanf("%d%d",&n,&m);

	    init();

 1	    for ( int i = 1 ; i <= m ; i++)
 2	    {
 3		int u,v;
 4		LL w;
 5		scanf("%d%d%lld",&u,&v,&w);
 6		addedge(u,v,w);
 7	    }
 8	    for ( int i = 1 ; i <= n ; i++)
 9	    {
10		int x;
11		scanf("%d",&x);
12		in[i] = x;
13		while (x--)
14		{
15		    int y ;
16		    scanf("%d",&y);
17		    prec[y].push_back(i);
18		}
19	    }
20	    LL ans = dij(1);
21	    printf("%lld\n",ans);
22	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}