您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

HDU 4370 0 or 1

2019-07-25【ACM||算法】人已围观

简介HDU 4370 0 or 1

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

using namespace std;

const int maxn = 310;
const int inf = 0x3f3f3f3f;

int n;
int vst[maxn];
int d[maxn];
int G[maxn][maxn];

void spfa(int s){
    queue<int> q;
    memset(vst, 0, sizeof(vst));
    for(int i = 1; i <= n; ++i){
        if(i == s)
            d[i] = inf;
        else{
            d[i] = G[s][i];
            q.push(i);
            vst[i] = 1;
        }
    }
    while(!q.empty()){
        int k = q.front();
        q.pop();
        vst[k] = 0;
        for(int j = 1; j <= n; ++j){
            if(d[j] > d[k] + G[k][j]){
                d[j] = d[k] + G[k][j];
                if(!vst[j]){
                    q.push(j);
                    vst[j] = 1;
                }
            }
        }
    }
}

int main(){
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                scanf("%d", &G[i][j]);
        spfa(1);
        int v1, v2, v3;
        v1 = d[n];
        v2 = d[1];
        spfa(n);
        v3 = d[n];
        int ans = min(v1, v2+v3);
        printf("%d\n", ans);
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:POJ 3169 Layout

下一篇:POJ 2236 Wireless Network

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00