k短路

无聊整理一下

 1 #include<bits/stdc++.h>
 2 #define clr(a,x) memset(a,x,sizeof(a))
 3 #define rep(i,l,r) for(int i=l;i<r;i++)
 4 typedef long long ll;
 5 using namespace std;
 6 int read()
 7 {
 8     char c=getchar();
 9     int ans=0,f=1;
10     while(!isdigit(c)){
11         if(c=='-') f=-1;
12         c=getchar();
13     }
14     while(isdigit(c)){
15         ans=ans*10+c-'0';
16         c=getchar();
17     }
18     return ans*f;
19 }
20 struct edge{
21     int d,to;
22 };
23 struct node{
24     int num,d;
25     inline bool operator <(const node&A)const{
26         return d>A.d;
27     } 
28 };
29 const int maxn=1009,inf=0x3fffffff;
30 int n,m,k,d[maxn];
31 priority_queue<node>Q;
32 vector<edge>e[maxn];
33 vector<edge>e1[maxn];
34 void dijkstra()
35 {
36     rep(i,i,n+1) d[i]=inf;
37     d[1]=0;
38     node start;
39     start.num=1,start.d=0;
40     Q.push(start);
41     while(!Q.empty()){
42         node now=Q.top();
43         Q.pop();
44         if(now.d==d[now.num]){
45             rep(i,0,e1[now.num].size()){
46                 if(d[now.num]+e1[now.num][i].d<d[e1[now.num][i].to]){
47                     d[e1[now.num][i].to]=d[now.num]+e1[now.num][i].d;
48                     node next;
49                     next.num=e1[now.num][i].to;
50                     next.d=d[e1[now.num][i].to];
51                     Q.push(next);
52                 }
53             }
54         }
55     }
56 }
57 void work()
58 {    
59     int cnt=0;
60     while(!Q.empty()) Q.pop();
61     node start;
62     start.num=n,start.d=d[n];
63     Q.push(start);
64     while(cnt<k&&!Q.empty()){
65         node now=Q.top();
66         Q.pop();
67         if(now.num==1){
68             ++cnt;
69             printf("%d
",now.d);
70         }else{
71             rep(i,0,e[now.num].size()){
72                 node next;
73                 next.num=e[now.num][i].to;
74                 next.d=now.d-d[now.num]+e[now.num][i].d+d[e[now.num][i].to];
75                 Q.push(next);
76             }
77         }
78     }
79     if(cnt<k) printf("-1
");
80 }
81 int main()
82 {    
83     n=read(),m=read(),k=read();
84     rep(i,0,m){
85         edge ed;
86         int from=read();
87         ed.to=read(),ed.d=read();
88         e[from].push_back(ed);
89         swap(ed.to,from);
90         e1[from].push_back(ed);
91     }
92     dijkstra();
93     work();
94     return 0;
95 }

View Code

跑步【STSR】Round #3

描述

有一个人，他在一座山上，他准备用从顶峰跑到山脚的方法来锻炼，而且只沿着下坡的路跑到山脚。山一共有M条路，每条路连接两个用1..N标号的地点，如果X>Y，则地点X大于地点Y的高度。但是因为他比较懒，所以他想跑最短的路径。但是很快他厌倦了一直走同一条路，

所以他想找出K条不同的路径并使得这K条路为最短的K条路径。

输入格式

第1行：三个数：N,M,K

第2..M+1行：每一行包含三个数x,y,d,表示有一条从x到y的路，路径长度为d，保证x>y

输出格式

第1..K行：第i行包含第i短路的长度(如果存在的话）。如果不存在第i短路的长度则输出-1

注意只输出一行-1。比如样例中没有第7和第8短路我们只输出一行-1 。

样例输入

5 8 8

5 4 1

5 3 1

5 2 1

5 1 1

4 3 4

3 1 1

3 2 1

2 1 1

样例输出

-1

数据范围与约定

对于30%的数据：0<=n<=100,0<=m<=10000,0<=k<=100
对于100%的数据：0<=n<=1000,0<=m<=10000,0<=k<=100

k短路