posts - 1,  comments - 1,  trackbacks - 0
Problem Description
虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……眼看寒假就快到了,这么一大段时间,可不能浪费啊,一定要给自己好好的放个假,可是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。
 

Input
输入数据有多组,每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个,草儿想去的地方有D个;
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。
 

Output
输出草儿能去某个喜欢的城市的最短时间。
 

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
 

Author
Grass
 

Source
 

Recommend
lcy

单源点最短路径问题。
d[i]用来保存起始点beg到点i的最短路径。
c[i][j]为边
<i,j>的权。
如果边
<i,j>不存在,则置c[i][j]=INF。
path[i]用来保存最短路径中点i的前一个顶点。

#include
<cstdio>
const int MAX = 10000;
const int INF = 1000000;
int d[MAX];
int c[MAX][MAX];
bool flag[MAX];
//int path[MAX];
int Dijkstra(int beg, int n)
{
    
int i, j, u, tmp;
    
for(i = 1; i <= n; i++)
    
{
        d[i] 
= c[beg][i];
        flag[i] 
= false;
        
/*if(d[i] == INF)
            path[i] = 0;
        else
            path[i] = beg;
*/

    }

    d[beg] 
= 0; flag[beg] = true;
    
for(i = 1; i <= n; i++)
    
{
        tmp 
= INF; u = beg;
        
for(j = 1; j <=n; j++)
        
{
            
if(!flag[j] && d[j] < tmp)
            
{
                u 
= j; 
                tmp 
= d[j];
            }

        }

        flag[u] 
= true;
        
for(j  = 1; j <= n; j++)
        
{
            
if(!flag[j] && c[u][j] < INF)
            
{
                
if(d[u] + c[u][j] < d[j])
                    d[j] 
= d[u] + c[u][j];
                
//path[j] = u;
            }

        }

    }

    
return 0;
}

int main()
{    
    
return 0;
}



#include <stdio.h>
#define Max 99999
int mp[1001][1001];
int main(void)
{
    
int i, j, k;
    
int x, y, cost;
    
int len, min;
    
int T, S, D;
    
int visit[1024];

    
while (scanf("%d%d%d"&T, &S, &D) != EOF)
    
{
        
for (i = 0; i < 1001; i++)
        
{
            
for (j = 0; j < 1001; j++)
                mp[i][j] 
= Max;
        }


        len 
= 0;

        
for (i = 0; i < T; i++)
        
{
            scanf(
"%d%d%d"&x, &y, &cost);
            
if (mp[x][y] > cost) mp[x][y] = mp[y][x] = cost;
            
if (len < x) len = x;
            
if (len < y) len = y;
        }


        
for (i = 0; i < S; i++)
        
{
            scanf(
"%d"&x);
            mp[
0][x] = 0;
        }


        
for (i = 0; i <= len; visit[i++= false);

        
for (i = 1; i <= len; i++)
        
{
            min 
= Max;
            
for (j = 1; j <= len; j++)
            
{
                
if (!visit[j] && min > mp[0][j])
                
{
                    min 
= mp[0][j];
                    k 
= j;
                }

            }

            
if (min == Max) break;
            visit[k] 
= true;
            
for (j = 1; j <= len; j++)
            
{
                
if (!visit[j] && mp[0][j] > mp[0][k] + mp[k][j])
                    mp[
0][j] = mp[0][k] + mp[k][j];
            }

        }


        min 
= Max;
        
for (i = 0; i < D; i++)
        
{
            scanf(
"%d"&x);
            
if (min > mp[0][x])
                min 
= mp[0][x];
        }

        printf(
"%d\n", min);
    }


    
return 0;
}

posted on 2009-06-01 09:48 Aiscanf 阅读(555) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

  • 1. re: wince中消息处理
  • winCE同样不接受窗口非客户区产生的消息,如WM_NCMOUSEMOVE
    我想当鼠标在非客户区移动是写些代码你有办法处理吗?有的话给我指点指点,
    crow024@163.com
  • --as