hdu

http://acm.hdu.edu.cn/showproblem.php?pid=2851

首先有n层,每层的路径都有一个起点和终点和对应的危险值,如果某两层之间有交集,就能从这一层上到另外一层,不过只能上不能下.

给定m个目标点求出到目标点的最小危险值.

因为权值不一样,所以不能用bfs,dijkstra就好。

建图就是把所有相连的边处理出来,因为读入是对y排序的.然后以此dijkstra就能求出所有点的最小花费。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <queue>
 5 using namespace std;
 6 const int maxn = 2010;
 7 const int INF = 1<<30;
 8 int n,m;
 9 struct node
10 {
11     int x,y,cost;
12 }f[maxn];
13 
14 struct edge
15 {
16     int to,cost;
17     edge(){}
18     edge(int x,int y) {
19         to=x;
20         cost=y;
21     }
22 };
23 typedef pair<int,int>P;
24 vector<edge>G[maxn];
25 int d[maxn];
26 void dijkstra(int s)
27 {
28     priority_queue<P,vector<P>,greater<P> >que;
29     for(int i=1;i<=maxn;i++) d[i]=INF;
30     d[s]=f[1].cost;
31     que.push(P(f[1].cost,s));
32 
33     while(!que.empty())
34     {
35         P p=que.top();que.pop();
36         int v=p.second;
37         if(d[v]<p.first) continue;
38         for(int i=0;i<G[v].size();i++)
39         {
40             edge e=G[v][i];
41             if(d[e.to]>d[v]+e.cost)
42             {
43                 d[e.to]=d[v]+e.cost;
44                 que.push(P(d[e.to],e.to));
45             }
46         }
47     }
48 }
49 
50 int main()
51 {
52     //freopen("a.txt","r",stdin);
53     int t,k;
54     scanf("%d",&t);
55     while(t--)
56     {
57         scanf("%d%d",&n,&m);
58         for(int i=1;i<=n;i++)
59         {
60             G[i].clear();
61             scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].cost);
62         }
63         //printf("%d
",n);
64         for(int i=1;i<=n;i++)
65         {
66             for(int j=i+1;j<=n;j++)
67                 if(f[j].x<=f[i].y)
68                 {
69                     G[i].push_back(edge(j,f[j].cost));
70                    // printf("%d %d %d
",i,j,p[i].cost+p[j].cost);
71                 }
72         }
73         dijkstra(1);
74         for(int i=0;i<m;i++)
75         {
76             scanf("%d",&k);
77             if(d[k]==INF) printf("-1
");
78             else
79             printf("%d
",d[k]);
80         }
81     }
82     return 0;
83 }