设为首页 加入收藏

TOP

最短路(一)
2019-05-23 14:55:30 】 浏览:117
Tags:短路

 

 

杭电oj ----2544

      深    搜

 

Accepted 2544 327MS 1768K 635 B C++

 

#include <cstdio>
#include <cstring>
const int INF=0x3f3f3f3f;
int n,m,a,b,c,mp[105][105],ans;
bool use[105];
void dfs(int k,int l){
        for(int i=2;i<=n;i++)
        {
                if(l>ans)   return;
                if(k==n)
                {
                        ans=l;
                        return;
                }        
                if(use[i]==false)
                {
                        use[i]=true;
                        dfs(i,l+mp[k][i]);
                        use[i]=false;
                 }
        }
}
int main()
{
        while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
        {
                ans=INF;
                memset(mp,INF,sizeof(mp));
                for(int i=1;i<=m;i++)
                {
                        scanf("%d%d%d",&a,&b,&c);
                        if(mp[a][b]>c)
                                mp[a][b]=mp[b][a]=c;
                }
                use[1]=true;
                dfs(1,0);
                printf("%d\n",ans);
        }
return 0;
}

 

 

     弗  洛  伊  德(Floyd)

Accepted 2544 31MS 1260K 600 B G++
#include <cstdio>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f;
int n,m,a,b,c,mp[105][105];
int main()
{
        int i,j,k;
        while(scanf("%d%d",&n,&m)!=EOF&&(m||n))
        {
                memset(mp,INF,sizeof(mp));
                for(int i=0;i<m;i++)
                {
                        scanf("%d%d%d",&a,&b,&c);
                        if(mp[a][b]>c)
                                mp[a][b]=mp[b][a]=c;
                }
                for(k=1;k<=n;k++)
                        for(i=1;i<=n;i++)
                                for(j=1;j<=n;j++)
                                        if(mp[i][k]+mp[k][j]<mp[i][j])
                                                mp[i][j]=mp[i][k]+mp[k][j];
                printf("%d\n",mp[1][n]);
        }
        return 0;
}

 

 第 杰 斯 特 拉

Accepted 2544 15MS 1260K 811 B G++

 

#include<cstdio>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int ans[105],n,m,mp[105][105],a,b,c;
bool use[105];
void dij(){
    for(int i=2;i<=n;i++)
        ans[i]=mp[1][i];
    ans[1]=0;
    memset(use,true,sizeof(use));
    use[1]=false;
    for(int i=2;i<n;i++)
    {
        int v,f=INF;
        for(int j=1;j<=n;j++)
            if(ans[j]<=f&&use[j])
            {
                f=ans[j];
                v=j;
            }
        for(int j=1;j<=n;j++)
            if(ans[v]+mp[v][j]<ans[j])
            ans[j]=ans[v]+mp[v][j];
        use[v]=false;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {
        memset(mp,INF,sizeof(mp));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(mp[a][b]>c)
               mp[a][b]=mp[b][a]=c;
        }
        dij();
        printf("%d\n",ans[n]);
    }
    return 0;
} 

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int mp[1002][1002];
bool use[1002];
int ans[1002];
const int INF  = 0x3f3f3f3f;
int n;
void dij(int a){
    ans[a] = 0;//设定起点 
    for(int i = 1 ; i < n ; i++){
        int min1 = INF,min2;
        for(int j = 1 ; j <= n ; j++){
            if(use[j] && ans[j] < min1){
                min1=ans[j];
                min2=j;
            }
        }
        use[min2]=false;
        for(int j=1;j<=n;j++){
            if(min1+mp[min2][j] < ans[j]){
                ans[j] = mp[min2][j] + min1;
            }
        }
    }
}
int main(){
    int t,s,d;
    while(scanf("%d%d%d",&t,&s,&d)!=EOF){
        memset(mp,INF,sizeof(mp));
        int x,y,time ;
        int max2 =0;
        for(int i = 0 ; i < t ; i++){
            scanf("%d%d%d",&x,&y,&time);
            int max1 = x > y ? x : y;
            max2 = max2 > max1 ? max2 : max1;
            if(mp[x][y]>time)
               mp[x][y]=mp[y][
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇友元函数破坏信息隐藏性 下一篇C++基础——类封装简单示例

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目