程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> P1828 香甜的黃油 Sweet Butter,p1828butter

P1828 香甜的黃油 Sweet Butter,p1828butter

編輯:C++入門知識

P1828 香甜的黃油 Sweet Butter,p1828butter


題目描述

農夫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號牧場最優

}

 

思路:SPFA+暴力,詳解請看字裡行間

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring> 
 4 #include<queue>
 5 #define maxn 0x7fffffff; 
 6 using namespace std;
 7 int num[10001];//儲存每一個牧場上的奶牛的數量
 8 int map[1001][1001];
 9 int a[1001][1001];//鄰接表
10 int numcishu[1001];//每一個點能到達的邊的數量 
11 int ans=maxn;//答案;
12 int minnow;//當前的最小值
13 int dis[1001];//儲存當前節點到其他節點的最短路 
14 int vis[1001];
15 queue<int>q;
16 int mc;//牧場數 
17 void spfa(int p)//計算p到其他點的路徑 
18 {
19     while(q.size()!=0)q.pop();
20     memset(dis,0x7f,sizeof(dis));
21     vis[p]=1;
22     dis[p]=0;
23     q.push(p);
24     while(q.size()!=0)
25     {
26         int k=q.front();
27         for(int j=1;j<=numcishu[k];j++)
28         {
29             if(dis[a[k][j]]>dis[k]+map[k][a[k][j]])//特別注意因為是鄰接表儲存所以j不一定是k能到達的邊 
30             {
31                 dis[a[k][j]]=dis[k]+map[k][a[k][j]];
32                 if(vis[a[k][j]]==0)
33                 {
34                     q.push(a[k][j]);
35                     vis[a[k][j]]=1;
36                 }
37             }
38         }
39         q.pop();
40         vis[k]=0;
41     }
42     minnow=0;
43     for(int i=1;i<=mc;i++)
44     {
45         minnow=minnow+dis[i]*num[i];    
46     }
47     if(minnow<ans)
48     ans=minnow;
49 }
50 int main()
51 {
52     memset(map,0x7f,sizeof(map));
53     int n;//奶牛數
54     
55     int m;//道路的數量 
56     scanf("%d%d%d",&n,&mc,&m);
57     for(int i=1;i<=n;i++)
58     {
59         int p;//奶牛所在牧場的號碼
60         scanf("%d",&p);
61         num[p]++; 
62     }
63     for(int i=1;i<=m;i++)
64     {
65         int x,y,z;
66         scanf("%d%d%d",&x,&y,&z);
67         map[x][y]=map[y][x]=z;
68         a[x][++numcishu[x]]=y;
69         a[y][++numcishu[y]]=x;
70     }
71     for(int i=1;i<=mc;i++)
72     {
73         spfa(i);
74     }
75     cout<<ans;
76     return 0;
77 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved