彩票平台:首页 > 学习之路 > ACM||算法ACM||算法

113彩票官网

卞振伟2019-05-07【ACM||算法】人已围观

简介不同算法实现,提升自我。

个人博客:www.dlxhly.com
如果你觉得对你有帮助,欢迎开奖记录查询[1]

113彩票官网

Floyd Dijkstra SPFA

希望能对你有所帮助

彩票开奖结果

 

 

POJ - 2387


#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int G[maxn][maxn];
int vst[maxn];
int d[maxn];
int m, n;

void Dijkstra(int s){
    for(int i = 1; i <= n; ++i){
        d[i] = inf;
        vst[i] = 0;
    }
    d[s] = 0;
    vst[s] = 1;
    for(int i = 0; i < n-1; ++i){
        int Min = inf;
        int k = s;
        for(int j = 1; j <= n; ++j){
            if(!vst[j] && Min > d[j]){
                Min = d[j];
                k = j;
            }
        }
        vst[k] = 1;
        for(int j = 1; j <= n; ++j){
            if(G[k][j])
                if(!vst[j] && d[j] > d[k]+G[k][j]){
                    d[j] = d[k] + G[k][j];
                }
        }
    }
}

int main(){
    while(~scanf("%d %d", &m, &n)){
        memset(G, 0, sizeof(G));
        for(int i = 0; i < m; ++i){
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            if( G[x][y] == 0 || (G[x][y] && v < G[x][y]) ){
                G[x][y] = v;
                G[y][x] = v;
            }
        }
        Dijkstra(1);
        printf("%d\n", d[n]);
    }
    return 0;
}
    

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n, m;
int G[maxn][maxn];
int d[maxn];
int vst[maxn];

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

int main(){
    while(~scanf("%d %d", &m, &n)){
        memset(G, 0, sizeof(G));
        for(int i = 0; i < m; ++i){
            int x, y, v;
            scanf("%d %d %d", &x, &y, &v);
            if(!G[x][y] || (G[x][y] && G[x][y] > v) ){
                G[x][y] = G[y][x] = v;
            }
        }
        spfa(1);
        printf("%d\n", d[n]);
    }
    return 0;
}
    

 


开奖记录查询

如果你觉得到该文章对你有帮助,欢迎开奖记录查询,有你的支持,我的个人博客一定会越来越好!

113彩票官网开奖记录查询码113彩票

Tags:编程   程序员   C|C++

很赞哦! ()

上一篇:简单搜索专题

下一篇:返回列表

文章评论

站点信息

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

客服在线

QQ客服

客服微信扫码

服务时间

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