文档章节

JZOJ3470 最短路

o
 osc_1ee7cxmx
发布于 2018/08/06 20:06
字数 636
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Description

  给定一个n个点m条边的有向图,有k个标记点,要求从规定的起点按任意顺序经过所有标记点到达规定的终点,问最短的距离是多少。

Input

  第一行5个整数n、m、k、s、t,表示点个数、边条数、标记点个数、起点编号、终点编号。

  接下来m行每行3个整数x、y、z,表示有一条从x到y的长为z的有向边。

  接下来k行每行一个整数表示标记点编号。

Output

  输出一个整数,表示最短距离,若没有方案可行输出-1。

Sample Input

  3 3 2 1 1
  1 2 1
  2 3 1
  3 1 1
  2
  3

Sample Output

  3

【样例解释】
  路径为1->2->3->1。

Data Constraint

  20%的数据n<=10。

  50%的数据n<=1000。

  另有20%的数据k=0。

  100%的数据n<=50000,m<=100000,0<=k<=10,1<=z<=5000。

 

Solution

  对每个特殊点跑一次spfa,因为k非常小,所以dfs特殊点得顺序。

 1 #include <cstdio>
 2 using namespace std;
 3 struct arr 
 4 { 
 5     int x,y,next;
 6     long long w;
 7 };
 8 arr edge[200000];
 9 int ls[200000],dis[60000],n,m,d[200000],k,a,b,s[20];
10 bool f[20];
11 long long dist[12][60000],min,cc;
12 int tt(int y,long long w,int c)
13 {
14     if (y==k)
15     {
16         if (w+dist[c][b]<min&&dist[c][b]!=cc)
17             min=w+dist[c][b];
18         return 0;
19     }
20     for (int i=2;i<=k+1;i++)
21         if (f[i])
22         {
23             f[i]=false;
24             if (dist[c][s[i]]!=c)
25                 tt(y+1,w+dist[c][s[i]],i);
26             f[i]=true;
27         }
28 }
29 int ss(int x,int y)
30 {
31     int h=0,t=1;
32     d[1]=x;
33     for (int i=1;i<=n;i++)
34         dist[y][i]=0xffffffff;
35     dist[y][x]=0;
36     while (h<=t)
37     {
38         int i=ls[d[++h]];
39         while (i!=0)
40         {
41             if (dist[y][edge[i].x]+edge[i].w<dist[y][edge[i].y])
42             {
43                 dist[y][edge[i].y]=dist[y][edge[i].x]+edge[i].w;
44                 d[++t]=edge[i].y;
45             }
46             i=edge[i].next;
47         }
48     }
49 }
50 int main()
51 {
52     scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
53     for (int i=1;i<=m;i++)
54     {
55         scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
56         edge[i].next=ls[edge[i].x];
57         ls[edge[i].x]=i;
58     }
59     ss(a,1);
60     for (int i=2;i<=k+1;i++)
61     {
62         scanf("%d",&s[i]);
63         ss(s[i],i);
64     }
65     min=0xffffffff;
66     cc=0xffffffff;
67     f[1]=false;
68     for (int i=2;i<=k+1;i++)
69     {
70         for (int j=2;j<=k+1;j++)
71             f[j]=true;
72         f[i]=false;
73         tt(1,dist[1][s[i]],i);
74     }
75     if (k==0) min=dist[1][b];
76     if (min==cc) printf("-1");
77     else
78     printf("%lld",min);
79 }
View Code

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

MongoDB入门系列——3.可视化工具篇

点击上方,轻松关注!! 前面我们已经介绍了MongoDB怎么安装,接下来要安装他的可视化工具——Studio 3T。 先到这下载一个压缩包,百度网盘,https://pan.baidu.com/s/1M8mlWo334KE8I1_UA2Da...

学习Java的小姐姐
2018/11/08
0
0
分层图的绘制 python(来自国外课程)

Exercise 10: Hierarchical clustering of the grain data In the video, you learnt that the SciPy linkage() function performs hierarchical clustering on an array of samples. Use th......

齐勇cn
24分钟前
13
0
微信小程序超简单的双向绑定(类似vue的v-model)

<input model:value="{{value}}" />

祖达
24分钟前
9
0
为什么AngularJS在select中包含一个空选项? - Why does AngularJS include an empty option in select?

问题: I've been working with AngularJS for the last few weeks, and the one thing which is really bothering me is that even after trying all permutations or the configuration de......

技术盛宴
27分钟前
13
0
centos宝塔面板安装及常见错误处理(超级详细)

原文连接:https://www.wjcms.net/archives/centos%E5%AE%9D%E5%A1%94%E9%9D%A2%E6%9D%BF%E5%AE%89%E8%A3%85%E5%8F%8A%E5%B8%B8%E8%A7%81%E9%94%99%E8%AF%AF%E5%A4%84%E7%90%86%E8%B6%85%E7%......

神兵小将
49分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部