POJ 1502 MPI MaeIstrom ( 裸最短路 || atoi系统函数 )

时间:2024-10-04 12:04:02

题意 : 给出 N 个点,各个点之间的路径长度用给出的下三角矩阵表示,上上角矩阵和下三角矩阵是一样的,主对角线的元素都是 0 代表自己到达自己不用花费,现在问你从 1 到 N 的最短路,矩阵的 x 代表点间无法互相到达

分析 : 最短路模板…… 就是在输入的时候需要将字符串变成整数、自己写也可以,也可以使用 atoi(char *)函数,其作用是将字符串数组变成整数,复杂度为 O(n)

#include<bits/stdc++.h>
using namespace std;
;
const int INF  = 0x3f3f3f3f;
typedef pair<int, int> HeapNode;

struct EDGE{ int v, nxt, w; };
int Head[maxn], Dis[maxn];
EDGE Edge[maxn*maxn];
int N, cnt;
inline void init()
{
    ; i<=N; i++)
        Head[i]=-, Dis[i]=INF;
    cnt = ;
}

inline void AddEdge(int from, int to, int weight)
{
    Edge[cnt].v = to;
    Edge[cnt].w = weight;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

int Dijkstra(int st)
{
    priority_queue< HeapNode, vector<HeapNode>, greater<HeapNode> > Heap;
    Dis[st] = ;
    Heap.push(make_pair(, st));
    while(!Heap.empty()){
        pair<int, int> T = Heap.top(); Heap.pop();
        if(T.first != Dis[T.second]) continue;
        ; i=Edge[i].nxt){
            int Eiv = Edge[i].v;
            if(Dis[Eiv] > Dis[T.second] + Edge[i].w){
                Dis[Eiv] = Dis[T.second] + Edge[i].w;
                Heap.push(make_pair(Dis[Eiv], Eiv));
            }
        }
    }
    ;
    ; i<=N; i++)
        ret = max(ret, Dis[i]);
    return ret;
}
];
int main(void)
{

    while(~scanf("%d", &N)){
        init();
        ; i<=N; i++){
            ; j<i; j++){
                scanf("%s", Digit);
                ] != 'x'){
                    int weight = atoi(Digit);
                    AddEdge(i, j, weight);
                    AddEdge(j, i, weight);
                }
            }
        }
        printf());
    }

    ;
}

相关文章