poj 1502 Dijstra

超、凢脫俗 2021-09-30 02:54 175阅读 0赞

这题是个简单的Dijkstra问题。关键是在输入。我的那个输入方法是看discuss别人给出的。如不用这个的话我们可以把字符串转换为数字。还有就是它题目要求的是到所有节点d的最短路径中最大的那个cost!

![2012042222350346.png][]

#include <iostream>
    #include <fstream>
    
    using namespace std;
    #define LEN 101
    #define INF (1<<30)
    #define MAX(a,b) (a>b?a:b)
    
    int n,dist[LEN];
    int map[LEN][LEN],maxcost;
    bool v[LEN];
    
    void Dijkstra()
    {
        int i,j,min,min_pos;
        maxcost=0;
        for(i=1; i<=n; i++)
        {
            dist[i]=map[1][i];
        }
        v[1]=true;
        for(i=1; i<n; i++)   //n-1
        {
            min=INF;
            for(j=2; j<=n; j++)  //寻找最小的
            {
                if(!v[j] && dist[j]<min)
                {
                    min=dist[j];
                    min_pos=j;
                }
            }
            v[min_pos]=true;
            maxcost=MAX(maxcost,dist[min_pos]);
            for(j=1; j<=n; j++)
            {
                if(!v[j] && dist[j]>dist[min_pos]+map[min_pos][j])
                {
                    dist[j]=dist[min_pos]+map[min_pos][j];
                }
            }
        }
    }
    
    
    int main()
    {
        int i,j,temp;
        freopen("acm.txt","r",stdin);
        scanf("%d",&n);
        memset(v,false,sizeof(v));
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=i; j++)
            {
                if(j==i)
                {
                    map[i][j]=0;
                }
                else if(scanf("%d",&temp)!=0)
                    map[i][j]=map[j][i]=temp;
                else
                {
                    map[i][j]=map[j][i]=INF;
                    scanf("x");
                }
            }
        }
        Dijkstra();
        printf("%d\n",maxcost);
        return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/04/22/2465600.html

[2012042222350346.png]: /images/20210725/88d81c80e053450fbdaa56ab287fd9ef.png