Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。
思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。
然后dij写得比较少。。。不是很熟练。。参考了这篇题解参考题解
思路倒是不难想，我在写spfa的时候也是这样想法，然后试图记录路径递归来搞。。。。。然而并不可以2333
也是第一次遇到带限制条件的最短路。。。还是多积累吧。。。
哦对了。。。权值比较大。。。要记得开long long
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月15日 星期五 00时32分14秒
4File Name :code/hdu/3873.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < long long ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=3E3+7;
34const int M=7E4+7;
35int n,m;
36int cnt;
37int head[N];
38int in[N]; //in[i]表示点i被几个点保护。。。
39vector <int>prec[N];
40LL d[N];
41bool vis[N];
42LL maxt[N];
43struct Edge
44{
45 int v;
46 LL w;
47 int nxt;
48}edge[M];
49
50
51void init()
52{
53 ms(head,-1);
54 ms(in,0);
55 cnt = 0 ;
56 for ( int i = 1 ; i <= n ; i++) prec[i].clear();
57}
58void addedge( int u,int v,int w)
59{
60 edge[cnt].v = v;
61 edge[cnt].w = w;
62 edge[cnt].nxt = head[u];
63 head[u]=cnt;
64 cnt++;
65}
66
67LL dij( int s)
68{
69 priority_queue<pi,vector<pi>,greater<pi> >q;
70 ms(d,0x3f);
71 ms(vis,false);
72 ms(maxt,0);
73
74 d[s] = 0 ;
75 q.push(make_pair(d[s],s));
76
77 while (!q.empty())
78 {
79 pi cur = q.top();
80 q.pop();
81 int u = cur.sec;
82 if (vis[u]) continue;
83 vis[u] = true;
84
85 int siz = prec[u].size();
86 for ( int i = 0 ; i < siz ; i++)
87 {
88 int v = prec[u][i];
89 in[v]--;
90 maxt[v] = max(maxt[v],d[u]);
91 if (d[v]!=inf&&!in[v])
92 {
93 d[v] = max(d[v],maxt[v]);
94 q.push(make_pair(d[v],v));
95 }
96
97 }
98 for ( int i = head[u] ; i != -1 ; i = edge[i].nxt)
99 {
100 int v = edge[i].v;
101 LL w = edge[i].w;
102 if (d[v]>d[u]+w)
103 {
104 d[v] = d[u] + w;
105 if (!in[v]) q.push(make_pair(d[v],v));
106 }
107 }
108 }
109 return d[n];
110
111}
112int main()
113{
114 #ifndef ONLINE_JUDGE
115 freopen("code/in.txt","r",stdin);
116 #endif
117
118 int T;
119 cin>>T;
120 while (T--)
121 {
122 scanf("%d%d",&n,&m);
123
124 init();
125
126 for ( int i = 1 ; i <= m ; i++)
127 {
128 int u,v;
129 LL w;
130 scanf("%d%d%lld",&u,&v,&w);
131 addedge(u,v,w);
132 }
133 for ( int i = 1 ; i <= n ; i++)
134 {
135 int x;
136 scanf("%d",&x);
137 in[i] = x;
138 while (x--)
139 {
140 int y ;
141 scanf("%d",&y);
142 prec[y].push_back(i);
143 }
144 }
145 LL ans = dij(1);
146 printf("%lld\n",ans);
147 }
148
149 #ifndef ONLINE_JUDGE
150 fclose(stdin);
151 #endif
152 return 0;
153}