最短路练习

9021#1259香甜的黄油

题目描述

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。 
农夫John很狡猾。像以前的Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入格式

第一行: 三个数：奶牛数N，牧场数（2<=P<=800），牧场间道路数C(1<=C<=1450)。
第二行到第N+1行: 1到N头奶牛所在的牧场号。
第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的。

输出格式

一行输出奶牛必须行走的最小的距离和。

样例

样例输入1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

样例输出1

8

数据范围与提示



{样例图形



          P2  

 P1 @--1--@ C1

         |

         | 

       5  7  3

         |   

         |     C3

       C2 @--5--@

          P3    P4

}

{样例输出说明：

  放在4号牧场最优

}
模板题了。稍微有点背景。
很好过，不多说。

给出点权。边权全部为1。求设在哪个牧场，牛的总移动距离最短。

无论是Floyd还是dijistra，都要有一步假设这个牧场为答案进行计算。不算不知道啊，所以几个牧场，几次计算。

对于Floyd，直接计算；对于dijstra，几个牧场，要跑几次单源最短路径，然后计算。

Floyd            

dijstra+堆优化

真是快的一批。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #define R register
 4 #define INF 0x7fffffff
 5 using namespace std;
 6 int ans=INF;
 7 int n,p,c,g[810][810],a[510];
 8 inline int ri(){
 9     char c=getchar();int x=0,w=1;
10     while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
11     while( isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
12     return x*w;
13 }
14 int main(){
15     int num,x,y;
16     for(R int i=1;i<=800;++i)
17     for(R int j=1;j<=800;++j)
18         g[i][j]=1000000;
19             
20     for(R int i=1;i<=800;++i)
21         g[i][i]=0;
22             
23     n=ri(),p=ri(),c=ri();
24     for(R int i=1;i<=n;++i)
25         num=ri(),a[num]++;
26             
27     for(R int i=1;i<=c;++i)
28         x=ri(),y=ri(),num=ri(),g[x][y]=g[y][x]=num;
29     
30     for(R int k=1;k<=p;++k)
31     for(R int i=1;i<=p;++i)
32     for(R int j=1;j<=p;++j)   
33         if(g[i][k]+g[k][j]<g[i][j])g[i][j]=g[i][k]+g[k][j];
34       for(R int i=1;i<=p;++i){
35           int tot=0;
36           for(R int j=1;j<=p;++j)tot+=g[i][j]*a[j];
37         ans=min(ans,tot);
38     }
39       printf("%d",ans);
40       return 0;
41 }
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <vector>
 5 #define MN 1000
 6 #define R register
 7 #define INF 0x7fffffff
 8 using namespace std;
 9 int n,m,c,d[MN],a[MN];
10 typedef pair<int ,int> p;
11 struct edge{int to,cost;};
12 vector <edge> G[MN];
13 inline int ri(){
14     char c=getchar();int x=0,w=1;
15     while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
16     while( isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
17     return x*w;
18 }
19 inline void dijstra(int x){
20     priority_queue<p,vector<p>,greater<p> >que;
21     fill(d+1,d+m+1,INF);
22     d[x]=0,que.push(p(0,x));//d[i],i
23     while(!que.empty()){
24         p q=que.top();que.pop();
25         int v=q.second;
26         if(d[v]<q.first)continue;
27         for(R int i=0;i<G[v].size();++i){
28             edge e=G[v][i];
29             if(d[e.to]>d[v]+e.cost){
30                 d[e.to]=d[v]+e.cost;
31                 que.push(p(d[e.to],e.to));
32             }
33         }
34     }
35 }
36 int main(){
37     int num,x,y,z;
38     n=ri(),m=ri(),c=ri();//奶牛数N，牧场数m，牧场间道路数C
39     for(R int i=1;i<=n;++i)num=ri(),a[num]++;
40     for(R int i=1;i<=c;++i){
41         x=ri(),y=ri(),z=ri();
42         edge e={y,z},u={x,z};
43         G[x].push_back(e);
44         G[y].push_back(u);
45     }
46     int ans=INF;
47     for(R int i=1;i<=m;++i){
48         int tot=0;
49         dijstra(i);
50         for(R int j=1;j<=m;++j)tot+=a[j]*d[j];
51         ans=min(ans,tot);
52     }
53     printf("%d",ans);
54 }

9021#1519最短路径

题目描述

相信对于最短路这个问题，你已经熟练掌握了。现在你有一个新的挑战：计算 Nya 图 上从 1 到 n 的最短路径。 Nya 图的定义如下：Nya 图是一种无向图。图中的每个节点属于一个层 x(1≤x≤n）， 共有 n 个节点。 你可以从层 x(1≤x≤n-1) 的任何节点到达层 x + 1 的任何节点，花费为 C，因为道 路是双向的，从层 x + 1(1≤x≤n-1) 的任何节点到达层 X 的任何节点也是相同的花费。 注意，有的层可能有多个节点，有的层可能一个节点都没有。 此外，有额外的 m 条边，每条边连接一对节点 u 和 v，通过的花费为 w。 现在请你帮助我们完成从节点 1 到节点 n 的最短路径的计算，使得路径的花费和最 小。

输入格式

从 nyagraph.in 中输入数据 输入有多组数据。 第一行，一个整数 T 表示数据组数。 对于每组数据，第一行为三个整数 n，m，C。 第二行为 n 个整数，第 i 个数表示第 i 个节点属于的层 xi(1≤xi≤n) 接下来 M 行，每行 3 个整数 u，v，w(1≤u，v≤n，u≠v)，表示一条额外边。 每组数据间有一个空行。

输出格式

输出到 nyagraph.out 中 对于每组数据，各输出一行。 每行先输出“Case #X:”，其中 X 为第几组数据，然后输出一个整数表示最小花费， 若不存在从 1 到 n 的最短路，输出-1。

样例

样例输入1

2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3
3 3 3
1 3 2
1 2 2
2 3 2
1 3 4

样例输出1

Case #1: 2
Case #2: 3

数据范围与提示

对于 30% 的数据：n≤100，m≤100，T = 1。
对于 70% 的数据：n≤1000，m≤10000。
对于 100% 的数据：n≤100000，m≤100000，1≤C≤10^3，1≤w≤10^4，T≤5。

这题只比模板多了一步复杂的预处理。emmm稍微复杂的？？

同一层的点，距离为0；与之相邻上下两层的点，距离为C。

于是就有一串恶心的edge e，ee，eee，eeee。。。

看着ppt码了个dijkstra（当然略有不同，变量名码风七七八八的，因为肯定不是看着打的...），

以及百度了一个spfa。spfa快...可能我写的丑。

dijkstra：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <vector>
 5 #define R register
 6 #define INF 0x7fffff
 7 using namespace std;
 8 int n,m,c,T,t;
 9 int num[100001],d[300111];
10 struct edge{int to,cost;};
11 vector<edge> G[300111];
12 typedef pair<int ,int> p;
13 inline void dijkstra(int x){
14     priority_queue<p,vector<p>,greater<p> >que;
15     for(R int i=1;i<=n*3+2;++i)d[i]=INF;
16     d[x]=0;que.push(p(0,x));
17     while(!que.empty()){
18         p q=que.top();que.pop();
19         int v=q.second;
20         if(d[v]<q.first)continue;
21         for(R int i=0;i<G[v].size();++i){
22             edge e=G[v][i];
23             if(d[e.to]>d[v]+e.cost){
24                 d[e.to]=d[v]+e.cost;
25                 que.push(p(d[e.to],e.to));
26             }
27         }
28     }
29 }
30 inline int ri(){
31     char c=getchar();int x=0,w=1;
32     while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
33     while( isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
34     return x*w;
35 }
36 int main(){
37     T=ri();
38     for(R int i=1;i<=T;++i){
39         t++;
40         for(R int i=1;i<=n*3+2;++i)G[i].clear();
41         n=ri(),m=ri(),c=ri();
42         for(R int i=1;i<=n;++i)num[i]=ri();
43         for(R int i=1;i<=n;++i){
44             int nm=num[i];
45             edge e={i,c},ee={nm+n+1,0},eee={i,0},eeee={nm+2*n+1,c};
46             G[nm+n].push_back(e);
47             G[i].push_back(ee);
48             G[nm+2*n+2].push_back(eee);
49             G[i].push_back(eeee);
50         }
51         for(R int i=1;i<=m;++i){
52             int u,v,w;
53             u=ri(),v=ri(),w=ri();
54             edge e={v,w},ee={u,w};
55             G[u].push_back(e);
56             G[v].push_back(ee);
57         }
58         dijkstra(1);
59         printf("Case #%d: ",t);
60         if(d[n]==INF)printf("-1
");
61         else printf("%d
",d[n]);
62     }
63     return 0;
64 }

spfa：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<queue>
 5 #include<cstring>
 6 #include<cstdlib>
 7 using namespace std;
 8 const int inf=2100000000;
 9 int ne,n,m,c;
10 int T;
11 bool vis[200004],use[200004];
12 int dis[200004];
13 int pos[200004];
14 int ra[200004];
15 struct data{
16        int von,w,next;
17 }e[4000004];
18 void insert(int u,int v,int w){
19      ++ne;
20      e[ne].w=w;
21      e[ne].von=v;
22      e[ne].next=pos[u];
23      pos[u]=ne;
24 }
25 queue<int>q;
26 void spfa(){
27     int w,u,v,i;
28     while(!q.empty())q.pop();
29     dis[1]=0; vis[1]=true; q.push(1);
30     while(!q.empty()){
31         u=q.front(); q.pop(); vis[u]=false; i=pos[u];
32         while(i!=0){
33             v=e[i].von;
34             w=e[i].w;
35             if(dis[v]>dis[u]+w){
36                 dis[v]=dis[u]+w;
37                 if(!vis[v]){vis[v]=true; q.push(v);}
38             }
39             i=e[i].next;    
40         }                      
41     }
42 }
43 int main(){
44     scanf("%d",&T);
45     for(int t=1;t<=T;t++){
46         memset(dis,127/3,sizeof(dis));
47         memset(vis,false,sizeof(vis));
48         memset(pos,0,sizeof(pos));
49         memset(use,false,sizeof(use));
50         ne=0;
51         scanf("%d%d%d",&n,&m,&c);
52         for(int i=1;i<=n;i++){scanf("%d",&ra[i]); use[ra[i]]=true;}
53         for(int i=1;i<n;i++){
54             if(use[i+1]&&use[i])
55                 insert(n+i+1,n+i,c),
56                 insert(n+i,n+i+1,c);             
57         }
58         for(int i=1;i<=n;i++){
59             insert(n+ra[i],i,0);
60             if(ra[i]<n)insert(i,n+ra[i]+1,c);
61             if(ra[i]>1)insert(i,n+ra[i]-1,c);
62         }
63         for(int i=1;i<=m;i++){
64             int u,v,w;
65             scanf("%d%d%d",&u,&v,&w);
66             insert(u,v,w);insert(v,u,w);
67         }
68         spfa();
69         if(dis[n]<inf)printf("Case #%d: %d
",t,dis[n]);
70         else printf("Case #%d: %d
",t,-1);
71     }
72     return 0;
73 }

P1875 佳佳的魔法药水

题目背景

发完了 k 张照片，佳佳却得到了一个坏消息：他的 MM 得病了！佳佳和大家一样焦急 万分！治好 MM 的病只有一种办法，那就是传说中的 0 号药水 ……怎么样才能得到 0 号药 水呢？你要知道佳佳的家境也不是很好，成本得足够低才行……

题目描述

得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去 买——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载：

1 份 A 药水混合 1 份 B 药水就可以得到 1 份 C 药水。（至于为什么 1+1=1，因为……这是魔 法世界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及 魔法书上所有的配置方法，现在要问的就是：1.最少花多少钱可以配制成功这种珍贵的药水；

2.共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为 不同的）。假定初始时你手中并没有任何可以用的药水。

输入输出格式

输入格式：

第一行有一个整数 N（N<=1000），表示一共涉及到的药水总数。药水从 0~N­1 顺序编号，0 号药水就是 最终要配制的药水。

第二行有 N 个整数，分别表示从 0~N­1 顺序编号的所有药水在魔法商店的价格（都表示 1 份的价格）。

第三行开始，每行有 3 个整数 A、B、C，表示 1 份 A 药水混合 1 份 B 药水就可以得到 1 份 C 药水。注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是 说不会出现某两行的 A、B 相同但 C 不同的情况。

输入以一个空行结束。

输出格式：

输出两个用空格隔开的整数，分别表示得到 0 号药水的最小花费以及花费最少的方案的个 数。

输入输出样例

输入样例#1： 
 
7 
10 5 6 3 2 2 3 
1 2 0 
4 5 1 
3 6 2
输出样例#1： 
 
10 3

说明

样例说明：

最优方案有 3 种，分别是：直接买 0 号药水；买 4 号药水、5 号药水配制成 1 号药水，直接 买 2 号药水，然后配制成 0 号药水；买 4 号药水、5 号药水配制成 1 号药水，买 3 号药水、6 号药水配制成 2，然后配制成 0。

既然把他标上了最短路的标签，那就不难想到以想象成连通图的方式，解决第一问。由于还要记录方案，不选择dijkstra。

spfa：

 1 #include <iostream>
 2 #include <cstdio> 
 3 #define R register
 4 #define INF 0x7fffff
 5 #define MN 1005
 6 using namespace std;
 7 int n,d[MN],ans[MN],g[MN][MN];
 8 bool vis[MN];
 9 inline int ri(){
10     char c=getchar();int x=0,w=1;
11     while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
12     while( isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
13     return x*w;
14 }
15 int main(){
16     n=ri();
17     for(R int i=1;i<=n;++i)d[i]=ri(),ans[i]=1;
18     int u,v,w;
19     while(scanf("%d%d%d",&u,&v,&w)==3)g[u+1][v+1]=g[v+1][u+1]=w+1;//+1变成习惯的储存方式
20     for(R int i=1;i<n;++i){
21         int tmp=INF;
22         for(R int j=1;j<=n;++j)if(!vis[j]&&d[j]<tmp)tmp=d[j],v=j;
23         vis[v]=1;
24         for(R int j=1;j<=n;++j)if(vis[j]&&g[v][j]){
25             if(d[v]+d[j]==d[g[v][j]])ans[g[v][j]]+=ans[v]*ans[j];
26             if(d[v]+d[j]<d[g[v][j]])d[g[v][j]]=d[v]+d[j],ans[g[v][j]]=ans[v]*ans[j];
27         }
28     } 
29     printf("%d %d",d[1],ans[1]);
30     return 0;
31 }

P4610 [COCI2011-2012#7] KAMPANJA

solution

题目背景

临近选举，总统要在城市111和城市222举行演讲。他乘汽车完成巡回演讲，从111出发，途中要经过城市222，最后必须回到城市111.特勤局对总统要经过的所有城市监控。为了使得费用最小，必须使得监控的城市最少。求最少要监控的城市。

题目描述

一共有NNN个城市，有MMM条有向边。(0<=N,M<=200)(0<=N,M<=200)(0<=N,M<=200) 有N从1出发途中要经过222，最后要回到1的路线中最少要经过的点的数目。

输入输出格式

输入格式：

第一行包含222个整数N,MN,MN,M。NNN表示城市的数目，MMM表示有向边的数目。 接下来MMM行，每行两个数A,BA,BA,B，表示从AAA到BBB有一条有向边。

输出格式：

最少要监控的城市的数量。

输入输出样例

输入样例#1： 
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3
输出样例#1： 
6

说明

0<=N,M<=2000<=N,M<=2000<=N,M<=200

本题数据加强by Imagine

CF95C Volleyball

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/flicker-five/p/10330351.html