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

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
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < long long ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=3E3+7;
const int M=7E4+7;
int n,m;
int cnt;
int head[N];
int in[N]; //in[i]表示点i被几个点保护。。。
vector <int>prec[N];
LL d[N];
bool vis[N];
LL maxt[N];
struct Edge
{
    int v;
    LL w;
    int nxt;
}edge[M];


void init()
{
    ms(head,-1);
    ms(in,0);
    cnt = 0 ;
    for ( int i = 1 ; i <= n ; i++) prec[i].clear();
}
void addedge( int u,int v,int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u]=cnt;
    cnt++;
}

LL dij( int s)
{
    priority_queue<pi,vector<pi>,greater<pi> >q;
    ms(d,0x3f);
    ms(vis,false);
    ms(maxt,0);

    d[s] = 0 ;
    q.push(make_pair(d[s],s));
    
    while (!q.empty())
    {
	pi cur = q.top();
	q.pop();
	int u = cur.sec;
	if (vis[u]) continue;
	vis[u] = true;

	int siz = prec[u].size();
	for ( int i = 0 ; i < siz ; i++)
	{
	    int v = prec[u][i];
	    in[v]--;
	    maxt[v] = max(maxt[v],d[u]);
	    if (d[v]!=inf&&!in[v])
	    {
		d[v] = max(d[v],maxt[v]);
		q.push(make_pair(d[v],v));
	    }

	}
	for  ( int i = head[u] ; i != -1 ; i = edge[i].nxt)
	{
	    int v = edge[i].v;
	    LL w = edge[i].w;
	    if (d[v]>d[u]+w)
	    {
		d[v] = d[u] + w;
		if (!in[v]) q.push(make_pair(d[v],v));
	    }
	}
    }
    return d[n];

}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	int T;
	cin>>T;
	while (T--)
	{
	    scanf("%d%d",&n,&m);
	    
	    init();

	    for ( int i = 1 ; i <= m ; i++)
	    {
		int u,v;
		LL w;
		scanf("%d%d%lld",&u,&v,&w);
		addedge(u,v,w);
	    }
	    for ( int i = 1 ; i <= n ; i++)
	    {
		int x;
		scanf("%d",&x);
		in[i] = x;
		while (x--)
		{
		    int y ;
		    scanf("%d",&y);
		    prec[y].push_back(i);
		}
	    }
	    LL ans = dij(1);
	    printf("%lld\n",ans);
	}

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}