hdu 3665 Seaside

思路：跑最短路即可
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int INF=1e9;
 5 const int N=1e5;
 6 
 7 //据输入第一个是N，然后是N组数据，第i组数据第一个是 Mi和Pi,
 8  //Mi代表城市i有多少条边，P代表是否与海边相邻，
 9  //然后接下来是MI组数据 每组 两个数 第一个表示城市编号L，
10  //i和这个城市相连，后面的数是DIS，代表L和i的权值。
11 
12 int n;
13 int dis[N],head[N],len;
14 bool vis[N];
15 int a[N];
16 
17 struct edge
18 {
19     int to,val,next;
20 }e[N];
21 
22 void init(){
23     memset(head,-1,sizeof(head));
24     len=0;
25     memset(a,0,sizeof(a));
26 }
27 void add(int from,int to,int  val)
28 {
29     e[len].to=to;
30     e[len].val=val;
31     e[len].next=head[from];
32     head[from]=len++;
33 }
34 struct point
35 {
36     int val,id;
37     point(int id,int val):id(id),val(val){}
38     bool operator <(const point &x)const{
39         return val>x.val;
40     }
41 };
42 void dijkstra(int s)
43 {
44     memset(vis,0,sizeof(vis));
45     for(int i=0;i<N;i++)
46         dis[i]=INF;
47     priority_queue<point> q;
48     q.push(point(s,0));
49     dis[s]=0;
50     while(!q.empty())
51     {
52         int cur=q.top().id;
53         q.pop();
54         if(vis[cur]) continue;
55         vis[cur]=true;
56         for(int i=head[cur];i!=-1;i=e[i].next)
57         {
58             int id=e[i].to;
59             if(!vis[id] && dis[cur]+e[i].val < dis[id])
60             {
61                 dis[id]=dis[cur]+e[i].val;
62                 q.push(point(id,dis[id]));
63             }
64         }
65     }
66 }
67 
68 int main(){
69     while(~scanf("%d",&n)){
70         init();
71         for(int i=0;i<n;i++){
72             int x,y,z,val;
73             scanf("%d%d",&x,&y);
74             a[i]=y;
75             for(int j=1;j<=x;j++){
76                 scanf("%d%d",&z,&val);
77                 add(i,z,val);
78                 add(z,i,val);
79             }
80         }
81         dijkstra(0);
82         int  Min=INF;
83         for(int i=0;i<n;i++){
84             if(a[i]){
85                 Min=min(Min,dis[i]);
86             }
87         }
88         cout<<Min<<endl;
89     }
90 }