第二次
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=2066
Name : 2066 一个人的旅行
Date : Friday, August 19, 2011
Time Stage : half an hour
Result:
4453342 2011-08-19 20:45:07 Accepted 2066
31MS 4200K 2070 B
C++ pyy
Test Data:
Review:
一开始忘记注释掉 freopen 函数了,结果悲剧地wrong answer
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define infinity 0x7f7f7f7f
#define minus_inf 0x80808080
#define MAXSIZE 1009
int road, neigh, dest, cityNum, minTime ;
int map[MAXSIZE][MAXSIZE], dp[MAXSIZE], used[MAXSIZE], want[MAXSIZE] ;
void dijkstra ()
{
int i, j ;
int minPath, iminPath ;
memset (used, 0, sizeof (used)) ;
// memset (dp, infinity, sizeof (dp)) ;
for (i = 1 ; i <= cityNum ; ++i)
dp[i] = map[0][i] ;
for (i = 1 ; i <= cityNum ; ++i)
{
minPath = infinity ;
iminPath = 0 ; // 这里不用也行,下面会给它赋值的
for (j = 1 ; j <= cityNum ; ++j)
{
if (!used[j] && dp[j] < minPath)
{
iminPath = j ;
minPath = dp[j] ;
}
}
used[iminPath] = 1 ;
for (j = 1 ; j <= cityNum ; ++j)
{
if (!used[j] && dp[iminPath] + map[iminPath][j] < dp[j])
dp[j] = dp[iminPath] + map[iminPath][j] ;
}
}
minTime = dp[want[1]] ;
for (i = 2 ; i <= dest ; ++i)
minTime = min (minTime, dp[want[i]]) ;
}
int main ()
{
// freopen ("C:\\in.txt", "r", stdin) ;
int i, j ;
int a, b, c ;
while (scanf ("%d%d%d", &road, &neigh, &dest) != EOF)
{
memset (map, infinity, sizeof (map)) ;
cityNum = 0 ;
for (i = 1 ; i <= road ; ++i)
{
scanf ("%d%d%d", &a, &b, &c) ;
map[a][b] = map[b][a] = min (map[a][b], c) ;
cityNum = max (cityNum, max (a, b)) ;
}
for (i = 1 ; i <= neigh ; ++i)
{
scanf ("%d", &a) ;
map[0][a] = map[a][0] = 0 ;
}
for (i = 1 ; i <= dest ; ++i)
{
scanf ("%d", &want[i]) ;
}
dijkstra () ;
printf ("%d\n", minTime) ;
}
return 0 ;
}
第一次
/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
URL :
Name :
Date : 2011/4/15 Friday
Time Stage :
Result:
00638009 2011-04-15 01:54:52 Accepted 1001 31 MS 4208 KB Visual C++ pyy
Test Data:
Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Sample Output
9
//----------------------------------------------------------------------------*/
#include <iostream>
#include <string.h>
using namespace std;
const int infinite = 0x08080808, maxSize = 1002;
int roads, neighbors, want, cost, maxPoint, minTrip;
int dp[maxSize], map[maxSize][maxSize], wanted[maxSize], mark[maxSize];
void dynamicProgramming()
{
int i, j, k, iminRoad = 0;
int minRoad;
memset( mark, 0, sizeof( mark ) );
for( i = 1; i <= maxPoint; i++ )
dp[i] = map[0][i];
for( i = 1; i <= maxPoint; i++ )
{
minRoad = infinite;
iminRoad = 0;
// 找到所有到0 点的路径中最短的
for( j = 1; j <= maxPoint; j++ )
{
if( !mark[j] && dp[j] < minRoad )
{
iminRoad = j;
minRoad = dp[j];
}
}
mark[iminRoad] = 1;
// 借助该最短路径,查找0 到其他点之间是否有最短路径
for( j = 1; j <= maxPoint; j++ )
{
if( !mark[j] && dp[iminRoad] + map[iminRoad][j] < dp[j] )
{
dp[j] = dp[iminRoad] + map[iminRoad][j];
}
}
}
// 查找0 到wanted 里面所有元素的路径中的最短路径
minTrip = dp[wanted[1]];
for( i = 2; i <= wanted[0]; i++ )
if( dp[wanted[i]] < minTrip )
minTrip = dp[wanted[i]];
}
int main()
{
int i, j, k;
while( cin >> roads >> neighbors >> want )
{
maxPoint = 0;
memset( map, infinite, sizeof( map ) );
for( i = 1; i <= roads; i++ )
{
cin >> j >> k >> cost;
map[j][k] = map[k][j] = min( cost, map[k][j] );
maxPoint = max( maxPoint, max( j, k ) );
}
for( i = 1; i <= neighbors; i++ )
{
cin >> j;
map[0][j] = map[j][0] = 0;
}
for( i = 1; i <= want; i++ )
{
cin >> wanted[i];
}
wanted[0] = want;
dynamicProgramming();
cout << minTrip << endl;
}
return 0;
}
分享到:
相关推荐
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
计算机网络复习大纲_杭电hdu.pdf
计算机网络复习大纲_杭电hdu借鉴.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
杭电ACMhdu1163
杭电hdu acm资料所用杭电的acm题
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
这个是杭电hdu的一个分类,新手们可以按照这个来刷题!
杭电acm培训课件 杭电acm培训课件 杭电acm培训课件 杭电acm培训课件
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
hdu杭电网络编程结课报告 聊天室
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
这是老师给我的哦,里面有完整版的HDU杭电ACM课件,还附有2000-2099的解题报告跟DP背包问题,如果你是acm的初学者,那么这是必须的,看了会有很大的帮助哦!
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告