- 浏览: 36739 次
- 性别:
- 来自: 杭州
最新评论
PAT1003 Emergency
- 博客分类:
- PAT
Sample Input
5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1
Sample Output
2 4
#include <iostream> using namespace std; #define INF 1000000 int Graph[500][500]; int TeamNum[500]; // 每个城市拯救队伍数目 int s[500]; // 判断是否已存入该点到S集合中 int Dist[500]; // 从v0到vi的最短路径长度 int TotalTeamNum[500]; // 从v0到k的拯救队伍数 int path[500]; // 最短路径的数目 void dijkstra(int v0, int N) { for(int i = 0; i < N; i++) //初始化 { Dist[i] = Graph[v0][i]; s[i] = 0; // 初始都未用过该点 TotalTeamNum[i] = TeamNum[v0] + TeamNum[i]; path[i] = 1; } // 依次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中 // 一旦S包含了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度 // 注意是从第二个节点开始,第一个为源点 s[v0] = 1; //v0加入到顶点集合S Dist[v0] = 0; TotalTeamNum[v0] = TeamNum[v0]; for(int i = 0; i < N; i++) { int min = INF, u = v0; for(int j = 0; j < N; j++) { // 找出当前未使用的点j的dist[j]最小值 // u保存当前邻接点中距离最小的点的号码 if(!s[j] && Dist[j] < min) { u = j; min = Dist[j]; } } s[u] = 1; //将u加入到集合S中 // 更新dist for(int k = 0; k < N; k++) { if(!s[k] && Graph[u][k] < INF && Dist[u] + Graph[u][k] < Dist[k]) { Dist[k] = Dist[u] + Graph[u][k]; TotalTeamNum[k] = TotalTeamNum[u] + TeamNum[k]; path[k] = path[u]; } else if(!s[k] && Graph[u][k] < INF && Dist[u] + Graph[u][k] == Dist[k]) { if(TotalTeamNum[k] < TotalTeamNum[u]+TeamNum[k]) //更新最大值 { TotalTeamNum[k] = TotalTeamNum[u]+TeamNum[k]; } path[k] = path[u] + path[k]; } } } } int main() { int N,M,C1,C2; cin>>N>>M>>C1>>C2; for(int i = 0; i < N; i++) { cin>>TeamNum[i]; } for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(i == j) { Graph[i][j]=0; } else { Graph[i][j]=INF; } } } for(int i = 0; i < M; i++) { int a,b,c; cin>>a>>b>>c; Graph[a][b]=Graph[b][a]=c; } dijkstra(C1,N); cout<<path[C2]<<" "<<TotalTeamNum[C2]; return 0; }
发表评论
-
PAT1013 Battle Over Cities
2012-11-29 23:59 779Sample Input 3 2 3 1 2 1 3 ... -
PAT1041 Be Unique
2012-11-23 23:43 762找出只出现过一次的数,用各种排序必然超时,需要用数组做hash ... -
PAT1042 Shuffling Machine
2012-11-23 23:42 736扑克洗牌 #include < ... -
PAT1040 Longest Symmetric String
2012-11-23 23:41 960求最长回文子串 #include < ... -
PAT1036 Boys vs Girls
2012-11-23 23:41 717Sample Input 1: 3 Joe M Mat ... -
PAT1035 Password
2012-11-23 23:40 619Sample Input 1: 3 Team0000 ... -
PAT1031 Hello World for U
2012-11-22 23:54 657Sample Input: helloworld! S ... -
PAT1029 Median
2012-11-22 23:54 655用标准库的排序全部超时,需要自己实现,另外还不能用cin co ... -
PAT1028 List Sorting
2012-11-22 23:53 810用vector最后一个用例超时了。。。 Sample ... -
PAT1027 Colors in Mars
2012-11-22 23:52 628Sample Input 15 43 71 Samp ... -
PAT1025 PAT Ranking
2012-11-22 23:51 775Sample Input: 2 5 123456789 ... -
PAT1023 Have Fun with Numbers
2012-11-21 23:55 690大数的相加 比较两个字符串中字符完全相同 Sa ... -
PAT1020 Tree Traversals
2012-11-21 23:54 654已知中序遍历 后序遍历,求层次遍历 Sample In ... -
PAT1019 General Palindromic Number
2012-11-21 23:53 539十进制转任意进制,并比较是否是回文数 Sample I ... -
PAT1037 Magic Coupon
2012-11-21 15:46 664Sample Input: 4 1 2 4 -1 ... -
PAT1038 Recover the Smallest Number
2012-11-20 23:52 1672由一道面试题改的 把数组排成最小的数 不同之处是这 ... -
PAT1024 Palindromic Number
2012-11-20 23:51 650Sample Input 1: 67 3 Sampl ... -
PAT1015 Reversible Primes
2012-11-19 23:51 772十进制转任意进制 假设十进制数为number,转 ... -
PAT1012 The Best Rank
2012-11-19 23:50 927四门功课,输出排名最高的是哪个 Sample Inpu ... -
PAT1011 World Cup Betting
2012-11-19 23:50 536Sample Input 1.1 2.5 1.7 1.2 ...
相关推荐
压缩包内直接保存的是各题源代码(题意请自行去网上查找),亲测有效
CAD填充图案(三百多种)-.pat文件 部分如下(篇幅有限) 2x12木地板.pat 45度人字形砖面(1).pat 8x8无缝砖.pat Z形砖.pat 丁字砖面1.pat 丁字砖面2.pat 三联蜂窝.pat 三角形拼铺.pat 不能通行的沼泽地.pat 乱沙.pat...
dcu2pat,make Delphi .dcu to .pat!! http://redplait.blogspot.com/2013/05/dcu2pat.html I wrote today some simple hack tool for creating signatures from delphi .dcu files for IDA flair The main idea is ...
PAT历年真题参考代码PAT历年真题参考代码PAT历年真题参考代码
浙大pat1002 C++代码
我的PAT乙级练习题1001代码记录,题目地址:https://www.patest.cn/contests/pat-b-practise/1001
浙大 机试 PAT 参考书 C++ /C语言编写
patb工程文件的说明文档,对patb工程文件的说明。adj、image、ori、cont。
为PAT考试作宣传用,希望广大的师生们,积极踊跃的参加
PAT甲级题目目录,按照一定规律分类,题目从新到旧1112 Stucked Keyboard (20 分)【将键盘坏损的地方修复】 1108 Finding Average (20 分)【读入有效的数字并处理输出无效的数字】 1100 Mars Numbers (20 ...
DSM_DS3622xs+_42951.pat
PAT甲级优秀辅导资料
pat.zju.edu.cn上面的大部分代码,基本上都是我自己写的,不过初期的...PAT (Advanced Level) Practise题组基本80个全了 PAT (Basic Level) Practise (中文)20个全了 《数据结构学习与实验指导》实验项目集也做了20个
黑群晖最经典的版本 DSM_DS918+_24922.pat
dait_pat1_pat1dait_pat1_pat1dait_pat1_pat1dait_pat1_pat1
PAT题解
Pat试题答案,题号从1001到1049,有需要的同学可以用来参考
photosh素材pat文件,
PAT甲级第1011题,之前自己做的时候写的代码,正确通过,但是效率不保证
Photoshop经典图案下载,绝对经典patPhotoshop经典图案下载,绝对经典pat