首页 > ACM题库 > 九度OJ > 九度-1341-艾薇儿的演唱会[最短路径]
2014
02-03

九度-1341-艾薇儿的演唱会[最短路径]

题目来自王道论坛计算机考研数据结构算法实战测试(2)

题目描述:
艾薇儿今天来到了中国,她计划两天后在哈尔滨举行一场个人的演唱会。由于出现了紧急情况,演唱会的举办方要求艾薇儿提前举行演唱会。艾薇儿现在在北京,她需要找出一条从北京到哈尔滨耗时最短的线路,以便尽快到达哈尔滨。
中国的铁路线非常复杂,有很多条路线可以从北京到达哈尔滨。艾薇儿在网上找到了铁路线各个线路上所需花费的时间,但是她还是看不出来哪一条线路可以最快地到达哈尔滨。你有办法帮助艾薇儿找出从北京到哈尔滨所需的最短时间吗?找出来的人可以免费获得现场演唱会门票一张哦。

输入:
 输入的第一行包括一个整数N(2<=N<=100),代表艾薇儿手上拿到的设有铁路站点的城市的个数,其中城市从1到n进行编号。以及M(1<=M<=1000),代表有M条铁路线路,每条铁路线路只连接两个城市。
接下来的一行有两个数,a和b(1<=a,b<=N),分别表示北京和哈尔滨的编号。
接下来有M行,每行有三个数x,y(1<=x,y<=N),t(1<=t<=1000),表示从城市x到城市y所需时间为t。

输出:
 请输出艾薇儿从北京到哈尔滨最少需要多长时间。你可以放心地认为肯定存在一条路线可以从北京到哈尔滨。

样例输入:
3 4
1 3
1 2 1
3 2 3
2 3 4
3 1 8
样例输出:
4
提示:
 1.火车能从城市x到城市y,就能从城市y到城市x,并且同一列火车来回所花费的时间是一样的。如果在x和y之间有不止一辆火车通行,则不同火车从x到y或者从y到x所花费的时间可能不相同。
2.虽然城市数有N个,但不保证所有的城市都能互相到达。可以保证的是,从北京到哈尔滨一定会有一条通路。

这里用Dijskra算法。

//copyright:www.acmerblog.com
#include<stdio.h>
#include<string.h>
#define INF 1001
int map[102][102], visit[102], spand[102];
int s, e, n, m;

void Dijkstra()
{
        int i, j, k, min;
        for(i = 1; i <= n; ++i)
                spand[i] = map[s][i];
        visit[s] = 1;
        spand[s] = 0;
        for(i = 2; i <= n; ++i)
        {
                k = -1, min = INF;
                for(j = 1; j <= n; ++j)
                {
                        if(!visit[j] && spand[j] < min)
                        {
                                k = j;
                                min = spand[j];
                        }
                }
                if(k == -1)
                        break;
                visit[k] = 1;
                for(j = 1; j <= n; ++j)
                {
                        if(!visit[j] && spand[k] + map[k][j] < spand[j])
                                spand[j] = spand[k] + map[k][j];
                }
        }
        printf("%d\n",spand[e]);
}

int main()
{
        while(scanf("%d%d%d%d", &n,&m,&s,&e) != EOF)
        {
                int i, j;
                memset(map, 0x3f, sizeof(map));
                memset(spand, 0x3f, sizeof(spand));
                memset(visit,0,sizeof(visit));
                int x, y, t;
                while(m--)
                {
                        scanf("%d%d%d", &x,&y,&t);
                        if(map[x][y] > t)
                                map[x][y] = map[y][x] = t;
                }
                Dijkstra();
        }
        return 0;
}
/**************************************************************
    Problem: 1341
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:70 ms
    Memory:1064 kb
****************************************************************/

 


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }