poj2263---dijkstra

毎日少しずつ進歩する
実は今日これを作った时はまだ小さくて得意げで、実は本当にとても良い感じがします~
poj 2263-これがdijkstraです
やはりこのブログはあまり使いません.少しずつ上達していきましょう~

#define LOCAL
#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAXN 200 + 10
#define MAXL 30 + 10

char cities[MAXN][MAXL];
int graph[MAXN][MAXN];

int FindCities(char *city, int j);
int Dijkstra(int start, int destination, int numberOfCities);

int main()
{
#ifdef LOCAL
    freopen("C:\\Users\\Administrator\\Desktop\\ACMTempIn.txt", "r", stdin);
    freopen("C:\\Users\\Administrator\\Desktop\\ACMTempOut.txt", "w", stdout);
#endif
    int numberOfRoads;
    int numberOfCities;
    char start[MAXL], destination[MAXL];
    int i,j,k;
    char city[MAXL];
    int cityIndex1;
    int cityIndex2;
    int result, count = 0;

    while(scanf("%d%d", &numberOfCities, &numberOfRoads) && numberOfRoads + numberOfCities != 0)
    {
        j = 0;
        count++;
        memset(graph, -1, sizeof(graph));
        for(i = 0; i < numberOfRoads; i++)
        {
            memset(city, -1, sizeof(city));
            scanf("%s", &city);
            if(FindCities(city, j) == -1)
            {
                strcpy(cities[j], city);
                j++;
            }
            cityIndex1 = FindCities(city, j);
            memset(city, -1, sizeof(city));
            scanf("%s", &city);
            if(FindCities(city, j) == -1)
            {
                strcpy(cities[j], city);
                j++;
            }
            cityIndex2 = FindCities(city, j);

            scanf("%d", &k);
            graph[cityIndex1][cityIndex2] = k;
            graph[cityIndex2][cityIndex1] = k;
        }
        scanf("%s%s", &start, &destination);
        cityIndex1 = FindCities(start, j);
        cityIndex2 = FindCities(destination, j);
        result = Dijkstra(cityIndex1, cityIndex2, numberOfCities);
        printf("Scenario #%d
%d tons

", count, result);
    }
    return 0;
}

int Dijkstra(int start, int destination, int numberOfCities)
{
    int bluePoint[MAXN];
    int redPoint[MAXN];
    int d[MAXN];
    int i,j;

    memset(bluePoint, 0, sizeof(bluePoint));
    memset(redPoint, 0, sizeof(redPoint));
    memset(d, 0, sizeof(d));

    //          
    redPoint[start] = 1;
    bluePoint[start] = 0;
    for(i = 0; i < numberOfCities; i++)
    {
        if(i != start)
            bluePoint[i] = 1;
    }

    //   d  
    for(i = 0; i < numberOfCities; i++)
        d[i] = graph[start][i];

    //     
    for(i = 1; i < numberOfCities; i++)
    {
        //         
        int max;
        int min;
        for(max = 0; !bluePoint[max];)max++;
        for(j = max; j < numberOfCities; j++)
            if(d[max] < d[j] && d[j] != -1)
                max = j;
        bluePoint[max] = 0;
        redPoint[max] = 1;

        for(j = 0; j < numberOfCities; j++)
        {
            if(d[max] > graph[max][j] && graph[max][j] != -1)
                min = graph[max][j];
            else
                min = d[max];

            if(min > d[j] && bluePoint[j] && graph[max][j] != -1)
                d[j] = min;
        }
    }
    return d[destination];
}

int FindCities(char *city, int j)
{
    int flag = 0;
    for(int i = 0; i < j + 1; i++)
    {
        if(!strcmp(city, cities[i]))
        {
            flag = i;
            return flag;
        }
    }
    return -1;
}