文档章节

JZOJ 3470. 【NOIP2013模拟联考8】最短路(path)

o
 osc_4nmshwhm
发布于 2018/08/06 21:49
字数 698
阅读 0
收藏 0

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

470. 【NOIP2013模拟联考8】最短路(path) (Standard IO)

Time Limits:  1000 ms  Memory Limits: 262144 KB  Detailed Limits  

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。
 
  做法:对每一个特殊点做最短路,然后枚举经过最短路的顺序。
 
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #define N 100007
 6 #define largest 100000000007
 7 using namespace std;
 8 int n, m, k, s, t, spe[15], tot, ls[N], cnt;
 9 long long ans, dis[N], d[15][15];
10 bool b[N], v[40];
11 queue<int> q;
12 
13 struct edge
14 {
15     int to, next, w;
16 }e[N];
17 
18 void add(int x, int y, int z)
19 {
20     e[++tot].to = y;
21     e[tot].w = z;
22     e[tot].next = ls[x];
23     ls[x] = tot;
24 }
25 
26 void spfa(int x)
27 {
28     memset(b, 0, sizeof(b));
29     for (int i = 1; i <= n; i++)
30         dis[i] = largest;
31     dis[x] = 0;
32     q.push(x);
33     while (!q.empty())
34     {
35         int now = q.front();
36         q.pop();
37         for (int i = ls[now]; i; i = e[i].next)
38         {
39             if (dis[now] + e[i].w < dis[e[i].to])
40             {
41                 dis[e[i].to] = dis[now] + e[i].w;
42                 if (!b[e[i].to])
43                 {
44                     q.push(e[i].to);
45                     b[e[i].to] = 1;
46                 }
47             }
48         }
49         b[now] = 0;
50     }
51     cnt++;
52     for (int i = 1; i <= k + 1; i++)
53         if (cnt != i)    d[cnt][i] = dis[spe[i]]; 
54     d[cnt][k + 2] = dis[t];
55 }
56 
57 void dfs(int dep, long long sum, int dc)
58 {
59     if (sum + d[dc][k + 2] > ans)    return;
60     if (dep >= k + 1)
61     {
62         if (sum + d[dc][k + 2] < ans)    ans = sum + d[dc][k + 2];
63         return;
64     }
65     for (int i = 2; i <= k + 1; i++)
66         if (!v[i])
67         {
68             v[i] = 1;
69             dfs(dep + 1, sum + d[dc][i], i);
70             v[i] = 0;
71         }
72 }
73 
74 int main()
75 {
76     scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
77     for (int i = 1; i <= m; i++)
78     {
79         int x, y, z;
80         scanf("%d%d%d", &x, &y, &z);
81         add(x, y, z);
82     }
83     for (int i = 2; i <= k + 1; i++)
84         scanf("%d", &spe[i]);
85     spe[1] = s;
86     for (int i = 1; i <= k + 1; i++)
87         spfa(spe[i]);
88     ans = largest;
89     dfs(1, 0, s);
90     if (ans < largest)    printf("%lld", ans);
91     else printf("-1");
92 }
View Code

 

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

暂无文章

Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 01:15 US Supreme Court deems half of Oklahoma a Native American Reservation - (reuters.com) 美国最高法院认为俄克拉荷马州的一半是印第安人保留地 得分:131 | 评...

FalconChen
47分钟前
16
0
OSChina 周五乱弹 —— 求求你吃了我吧,不要再玩弄食物的感情了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @巴拉迪维 :张喆的单曲《陷阱 》 这首歌已经在网易找不到原唱了,不知道被哪家买了版权。#今日歌曲推荐# 《陷阱 》- 张喆 手机党少年们想听歌...

小小编辑
58分钟前
24
1
清华陈文光教授:AI 超算基准测试的最新探索和实践。

道翰天琼认知智能平台为您揭秘新一代人工智能。 无规矩不成方圆。放在超级计算机的研发领域,没有一个大家普遍接受的算力评测指标,便难以推动超算迅猛发展。 而现在伴随着人工智能的发展,大...

jackli2020
今天
7
0
@RequestMapping, consumes 提交简单有意思的测试

getParm @GetMapping("getParm")public Result getParm(String id){ System.out.println(); return ResultFactory.success(id);} 等同于 == bodyParm @PostMapping("bodyParm......

莫库什勒
今天
25
0
63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
今天
55
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部