POJ 1502_Dijkstra

/*[任务]dijkstra (单源最短路，图中不能有负权的边。) [perfect!]
*[说明]Dijkstra算法按从源点src到其他各点的最短路径长度递增的顺序，依次确定src到每个点的最短路。
* 首先将dis[src]赋为0,其余点的dis赋为INF，此时所有点的最短路都还未确定。之后，每次在还未
* 确定最短路的点中，取一个当前已得的所有可能的路径长度中最短的那个点确定，设此点为mark.
* 然后对所有与mark相连的点进行松弛操作，即对于边(mark,v),判断dis[v]是否大于dis[mark]+g[mark][v],
* 若是，则更新dis[v]为dis[mark]+g[mark][v]。如此做N遍后，即确定了src到所有N个点的最短距离。
*[接口]void dijkstra(int src, int p); p 代表图中的点为从点 1 到点 p。src 为源点
*复杂度：O(n^2)可以堆优化，O(n+m)logn。
*输入：n 全局变量，图中的点数
* g 全局变量，g[i][j]表示i到j之间边的距离
*输出：dis全局变量，dis[i]表示节点src到i的最短距离
*/

题意：求点1 到其他点的最短路径，然后取它们中的最大值即可

由于矩阵是对称的，所以题目只给了一个下三角矩阵。

	1	2	3	4	5
1	0	50	30	100	10
2	50	0	5	20	x
3	30	5	0	50	x
4	100	20	50	0	10
5	10	x	x	10	0

/**********************************
    Subject: POJ 1502_Dijkstra
    Author : a_clay
    Created Date : 2014-05-06
*********************************/
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1000;
const int INF = 0x7fffffff;

int dis[N], g[N][N], n;
bool vis[N];
char str[10];

bool isdec(char str[]) {
    if(str[0] != 'x') return true;
    return false;
}

void dijkstra(int src, int p) {
    for (int i = 1; i <= p; ++i) dis[i] = INF;
    dis[src] = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= p; ++i) {
        int mark = -1, mindis = INF;
        for (int j = 1; j <= p; ++j) {
            if (!vis[j] && dis[j] < mindis) {
                mindis = dis[j];
                mark = j;
            }
        }
        vis[mark] = 1;
        for (int j = 1; j <= p; ++j)
            if (!vis[j])
                if (dis[mark] + g[mark][j] > 0)
                    dis[j] = min(dis[j], dis[mark] + g[mark][j]);
    }
}
int main() {
    int i, j;
    while(cin >> n) {
        memset(g, 0, sizeof(g));
        for(i = 2; i <= n; i++) {
            for(j = 1; j < i; j++) {
                cin >> str;
                int temp = INF;
                if(isdec(str)) {
                    sscanf(str, "%d", &temp);
                }
                g[i][j] = temp;
                g[j][i] = temp;
            }
        }
        dijkstra(1, n);
        int MAX = 0;
        for(i = 1; i <= n; i++) {
            MAX = max(dis[i], MAX);
        }
        cout << MAX << endl;
    }
    return 0;
}
// 12845965	a_clay	1502	Accepted	4636K	16MS	G++	1671B	2014-05-06 20:12:25