Day4-B-最短路径问题 HDU3790

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)Output输出一行有两个数，最短距离及其花费。Sample Input

Sample Output

9 11

思路：最短路问题，Djikstra即可，注意读入可能有重复边，需要判断一下，代码如下：

const int maxm = ;

const int INF = 0x7fffffff;

int N, M, Start, End, G[maxm][maxm], len[maxm][maxm], vis[maxm], cost[maxm], steps[maxm];

struct Node {

    int u, sum, step;

    Node(int _u, int _sum, int _step) : u(_u), sum(_sum), step(_step){}

    bool operator<(const Node &a) const {

        return a.sum < sum || (a.sum == sum && a.step < step);

    }

};

void init() {

    for (int i = ; i <= N; ++i) {

        cost[i] = steps[i] = INF;

        for (int j = ; j <= N; ++j)

            G[i][j] = G[j][i] = len[i][j] = len[j][i] = INF;

    }

    memset(vis, , sizeof(vis));

}

int main() {

    while(scanf("%d%d",&N,&M) && N + M) {

        init();

        for (int i = ; i < M; ++i) {

            int t1, t2, t3, t4;

            scanf("%d%d%d%d", &t1, &t2, &t3, &t4);

            if(G[t1][t2] > t3 || (G[t1][t2] == t3 && len[t1][t2] > t4)) {

                G[t1][t2] = G[t2][t1] = t3;

                len[t1][t2] = len[t2][t1] = t4;

            }

        }

        scanf("%d%d", &Start, &End);

        priority_queue<Node> q;

        q.push(Node(Start, , ));

        cost[Start] = steps[Start] = ;

        while(!q.empty()) {

            Node p = q.top();

            q.pop();

            if(vis[p.u]++)

                continue;

            for (int i = ; i <= N; ++i) {

                if(G[p.u][i] != INF) {

                    if(cost[i] > cost[p.u] + G[p.u][i] || (cost[i] == cost[p.u] + G[p.u][i]

                        && steps[i] > steps[p.u] + len[p.u][i])) {

                        cost[i] = cost[p.u] + G[p.u][i];

                        steps[i] = steps[p.u] + len[p.u][i];

                        q.push(Node(i, cost[i], steps[i]));

                    }

                }

            }

        }

        printf("%d %d\n", cost[End], steps[End]);

    }

    return ;

}

巴特西

Day4-B-最短路径问题 HDU3790

最新文章

热门文章