Dijkstra——去北京看奥运

Description

2008年将到，王飞同学化了九牛二虎之力搞到了2张2008年奥运会足球赛决赛的门票。真是开心啊！他爸爸准备开车跟他一起去北京看球赛。不过门票费好贵啊，所以他爸爸说了，这个钱要在下学期的生活费里扣（好抠门），不过如果他能让从杭州去北京的油费最省（油价最近涨的好厉害啊），那么就不扣生活费了。哈哈，这个就难不倒他了。在ACM里可不是白混的。很快他算出了汽车从杭州到北京必须要加几次油，并查出了到北京要经过哪几个城市，每个城市有哪些加油站以及从某城市各加油站到另一城市各加油站的距离和路况算出了各加油站之间的耗油量。下面是不是很easy?

Input

有多个测试案例。第一行先输入测试案例的数目T。对于每个测试案例，第一行输入一个整数n表示将在中途n（0 < n < 40)个城市中加油，后面紧跟着是n个整数代表每个城市有几个加油站(每个城市加油站不超过10个）。以下n+1行，每行由3个S_i,E_j,L一组组成的好几对整数，该行以0结束。表示从前一城市S_i第i个加油站（杭州的话就是家拉）出发到该城市第j个加油站消耗的油量为L升。

Output

对于每个测试，输出一行，内容为最小总耗油量。

Sample Input

1
2 2 3
1 1 3 1 2 1 0
1 1 2 1 2 7 2 1 8 2 2 9 2 3 4 0
1 1 5 2 1 6 3 1 6 0

Sample Output

10
看该题之前先弄清楚dijkstra算法，先看道简单的题
一共有n个顶点，共m条边，每条边由三个数据组成x,y,z，分别表示开始，结束，和需要走的路程，要求输出最短路程走到最终n
7 10
1 2 3
1 3 1
2 4 2
2 5 7
3 4 8
3 5 9
3 6 4
4 7 5
5 7 6
6 7 6

#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f, MAX = 300;
int min1,x,y,z,k,n,m;
int map[MAX][MAX],p[MAX],d[MAX];
void dijkstra(int map[][MAX],int n)
{
    for(int i = 1; i <= n ; i++)
        d[i] = inf;
    d[1] = 0;
    for(int i = 1; i <= n ; i++){
            min1 = inf;
          for(int j = 1; j <= n ; j++){
                if(!p[j] && d[j] < min1){
                     min1 = d[j];
                     k = j;
                }
          }
          p[k] = 1;
          for(int j = 1; j <= n ; j++){
                if(!p[j] && d[j] > d[k] + map[k][j])
                    d[j] = d[k] + map[k][j];
          }
    }
    printf("%d",d[n]);
}
int main(){
    memset(p,0,sizeof(p));
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n ; j++)
          map[i][j] = inf;
    for(int i = 1; i <= m ; i++){
        scanf("%d%d%d",&x,&y,&z);
        map[x][y] =z;
    }
    dijkstra(map,n);
    return 0;
}

View Code

dijkstra算法是用来算从一个顶点到另一个顶点最短路径的算法，用p来记忆是否走过这条路，用d来记忆最短路径，map用来记忆从x到y需要走的路程。

p先清零，然后在第一个小for循环中得到最小的路径的下标，将这个点记录下来已经走过了，第二个for用来更新从起点开始的最短路，的d[1] = 0，即从1点开始走，将map全都初始化为无穷大，那么在记录数据的时候真正记录的就有了长度，而无穷大就看做是不能走。

现在看原题。

题意：从一个起始点开始走，中间有好多点，要求最后走到终点。

难在输入。开始输入测试组，再输入有几个城市，每个城市分别得加油站的个数。在下一行输入每个加油站的起点和终点以及距离，最后输出。

#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f,MAX = 300;
int min1, n, m,i, j, k, x, y, z;
int map[MAX][MAX],p[MAX],d[MAX];

void dijkstra(int map[MAX][MAX],int n)
{
    d[1] = 0;
    for(int i = 1; i <= n; i++){
         min1 = inf;
       for(int j = 1; j <= n ;j++){
            if(!p[j] && d[j] > min1){
                    d[j] = min1;
                    k = j;
            }
       }
       p[k] = 1;
       for(int j = 1; j <= n; j++)
           if(!p[j] && d[j] > d[k] + map[k][j]);
              d[j] = d[k] + map[k][j];
    }
    printf("%d
",d[n]);
}

int main()
{
    int T,m,t[MAX],t1[MAX],temp;
    scanf("%d",&T);
    while(T--){
            n = 0;
            t[1] = 1;
            t1[1] = 0;
            t1[0] =0;
            scanf("%d",&m);
           for(int i = 2; i <= m+1 ; i++){
            scanf("%d",&t[i]);
            n+=t[i];//n用来储存所有的个数
           }
           n+=2;
           for(int i = 0; i <= n ; i++)
            for(int j = 0; j <= n; j++)
               map[i][j] = inf;
           for(int i = 2; i <= m+1; i++)
             for(int j = 1; j < i ;j++)
                 t1[i] += t[j];//t1用来出储存前面的个数,t用来储存当前的个数
           for(int i = 2; i <= m+2; i++){
                for(int k = 1; k <= t[i]; k++){
                        scanf("%d%d%d",&x,&y,&z);
                        map[t1[i-2]+x][t1[i-1]+y] = z;
                }
                scanf("%d",temp);
           }
           memset(p,0,sizeof(p));
          dijkstra(map,n);
    }
    return 0;
}

View Code

没有过的码-0-心烦晚点再改，输入一直错误。