Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

有大佬知道这个代码为啥SPFA过了,堆优化的dijk TLB了?

Posted by U201814778 at 2020-12-12 21:35:01 on Problem 3159
//
// Created by confidentOH on 2020/12/12.
//  candies
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <iterator>

using namespace std;

struct Edge{
    int v;
    int weight;
    int next;
};

typedef pair<int, int> P;
Edge Vs[150010];
int e;
int head[30010];
bool vis[30010];
int dist[150010];

void dijskra(int start, int n){
    dist[start] = 0;
    priority_queue<P> distances;
    P item;
    distances.push(P(dist[start], start));
    while(!distances.empty()){
        item = distances.top();
        distances.pop();
        int s = item.second;
        if(dist[s]<item.first){
            continue;
        }
        for(int i = head[s]; i!=-1; i = Vs[i].next){
            if(dist[i]>item.first+Vs[i].weight){
                dist[Vs[i].v] = item.first+Vs[i].weight;
                distances.push(P(dist[Vs[i].v], Vs[i].v));
            }
        }
    }
}

void SPFA(int start, int N){
    memset(vis, 0, sizeof(vis));
    stack<int> edges;
    edges.push(start);
    vis[start] = true;
    dist[start] = 0;
    while(!edges.empty()){
        int item = edges.top();
        edges.pop();
        vis[item] = false;
        for(int i = head[item]; i!=-1; i = Vs[i].next){
            if(dist[Vs[i].v]>dist[item]+Vs[i].weight){
                dist[Vs[i].v] = dist[item]+Vs[i].weight;
                if(!vis[Vs[i].v]){
                    edges.push(Vs[i].v);
                    vis[Vs[i].v] = true;
                }
            }
        }
    }
}

int main()
{
    int N, M;
    int start, end, w;
    while(~scanf("%d %d", &N, &M)){
        memset(head, -1, sizeof(head));
        e = 0;
        for(int i = 0; i<=N; i++){
            dist[i] = INT_MAX;
        }
        for(int i = 0; i<M; i++){
            scanf("%d %d %d", &start, &end, &w);
            Vs[e].v = end;
            Vs[e].weight = w;
            Vs[e].next = head[start];
            head[start] = e;
            e++;
        }
        SPFA(1, N);
        printf("%d\n", dist[N]);
    }
    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator