代码如下,介绍改天补上

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100005;
const int inf = 2147483647;

int cnt = 0;
int root[maxn],/*vis[maxn],*/cost[maxn],indegree[maxn];

struct Graph{ 
    int next,cost,pointer;
}edge[maxn<<5];

void add(int start,int to,int cost){
    edge[++cnt].cost = cost;
    edge[cnt].next = root[start];
    edge[cnt].pointer = to;
    root[start] = cnt;
    indegree[to]++;
    return;
}

void tops(int start){
    queue <int> task;
    task.push(start);
    cost[start] = 0;
    while(!task.empty()){
        start = task.front();
        task.pop();
        for(int i = root[start];i;i = edge[i].next){
            indegree[edge[i].pointer]--;
            if(indegree[edge[i].pointer]==0){
                task.push(edge[i].pointer);
                indegree[edge[i].pointer]--;
            }
            if(cost[edge[i].pointer]>edge[i].cost+cost[start]){
                cost[edge[i].pointer] = edge[i].cost+cost[start];
            }
        }
    }
    return;
}

int main(){
    int n,m,start;
    int f,g,w;
    memset(root,0,sizeof(root));
    memset(indegree,0,sizeof(indegree));
    cin>>n>>m>>start;
    for(int i = 1;i<=n;i++){
        cost[i] = inf;
    }
    for(int i = 1;i<=m;i++){
        cin>>f>>g>>w;
        add(f,g,w);
    }
    tops(start);
    for(int i = 1;i<=n;i++){
        cout<<cost[i]<<" ";
    }
    return 0;
}

 

打赏 赞(0)
支付宝二维码图片

支付宝扫描二维码打赏

发表评论

电子邮件地址不会被公开。

Scroll Up