当前位置: 58彩票app下载 > 关于计算机 > 正文

最短路计算代码库

时间:2019-09-23 23:31来源:关于计算机
【SinGuLaRiTy-1002】 Copyright (c) SinGuLaRiTy 2017. All RightsReserved. [SinGuLaRiTy] 最短路计算代码库,singularity代码库 【SinGuLaRiTy-1002】 Copyright (c) SinGuLaRiTy 2017. All RightsReserved. Dijkstra: 标题陈诉   有向

【SinGuLaRiTy-1002】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

[SinGuLaRiTy] 最短路计算代码库,singularity代码库

【SinGuLaRiTy-1002】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

Dijkstra:

标题陈诉

 

有向图的单起点最短路难题(Dijkstra算法)

 

输入

 

第1行:2个空格分开的整数n(2<=n<=500)和m(10<=m<=30000),分别代表图的顶点数和边数。

第2..m+1行:每行3个空格分开的平头i,j, w。i表示一条边的起源,j表示终点, w代表权值。

第m+2行:2个整数s,t(1<=s,t<=n),表示内定的极端。

 

输出

 

第1行:最小距离

第2行:最短路线(从源点到极限的体系,用1个空格分开)

 

 

样例输入 样例输出

5 7

1 2 10

1 4 30

1 5 100

2 3 50

3 5 10

4 3 20

4 5 60

1 5

60

1 4 3 5

 

 

 

 

 

 

 

 

 

 

 

代码:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int G[501][501],dis[501],L[501];
bool used[501];
void Dijkstra(int s)
{
    for(int i=1;i<=n;i++)
    {
        used[s]=1;
        for(int j=1;j<=n;j++)
        {
            if(G[s][j]==0||s==j)
                continue;
            if(dis[j]>dis[s]+G[s][j])
                dis[j]=dis[s]+G[s][j],L[j]=s;
        }
        int themin=0x3f3f3f3f;
        for(int i=1;i<=n;i++)                
            if(used[i]==0&&dis[i]<themin)
                s=i,themin=dis[i];
    }
}
int main()
{
    int a,b,c,S,E,cnt=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        G[a][b]=c;
    }
    scanf("%d%d",&S,&E);
    int e=E;
    dis[S]=0;
    for(int i=1;i<=n;i++)
        if(i!=S) dis[i]=0x3f3f3f3f;  

    Dijkstra(S);

    printf("%dn",dis[E]);
    while(L[E]!=0)
    {
        dis[cnt++]=L[E];
        E=L[E];
    }
    for(int i=cnt-1;i>=1;i--)
        printf("%d ",dis[i]);
    printf("%d",e);
    return 0;
}

 

Dijkstra:

标题汇报

 

有向图的单起点最短路难点(Dijkstra算法)

 

输入

 

第1行:2个空格分开的整数n(2<=n<=500)和m(10<=m<=两千0),分别表示图的顶点数和边数。

第2..m+1行:每行3个空格分开的整数i,j, w。i表示一条边的源点,j表示终点, w代表权值。

第m+2行:2个整数s,t(1<=s,t<=n),表示钦命的终极。

 

输出

 

第1行:最小距离

第2行:最短路线(从起源到终点的行列,用1个空格分开)

 

 

样例输入 样例输出

5 7

1 2 10

1 4 30

1 5 100

2 3 50

3 5 10

4 3 20

4 5 60

1 5

60

1 4 3 5

 

 

 

 

 

 

 

 

 

代码:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int G[501][501],dis[501],L[501];
bool used[501];
void Dijkstra(int s)
{
    for(int i=1;i<=n;i++)
    {
        used[s]=1;
        for(int j=1;j<=n;j++)
        {
            if(G[s][j]==0||s==j)
                continue;
            if(dis[j]>dis[s]+G[s][j])
                dis[j]=dis[s]+G[s][j],L[j]=s;
        }
        int themin=0x3f3f3f3f;
        for(int i=1;i<=n;i++)                
            if(used[i]==0&&dis[i]<themin)
                s=i,themin=dis[i];
    }
}
int main()
{
    int a,b,c,S,E,cnt=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        G[a][b]=c;
    }
    scanf("%d%d",&S,&E);
    int e=E;
    dis[S]=0;
    for(int i=1;i<=n;i++)
        if(i!=S) dis[i]=0x3f3f3f3f;  

    Dijkstra(S);

    printf("%dn",dis[E]);
    while(L[E]!=0)
    {
        dis[cnt++]=L[E];
        E=L[E];
    }
    for(int i=cnt-1;i>=1;i--)
        printf("%d ",dis[i]);
    printf("%d",e);
    return 0;
}

 

SPAF:

难点汇报

有向图的单起点最短路线难点。源点编号为1,终点编号为n。

输入

第1行:2个空格分开的整数n(2<=n<=5000)和m(10<=m<=五千00),分别代表图的顶点数和边数。

第2..m+1行:每行3个空格分开的平头i,j, w。i表示一条边的起源,j表示终点, w表示权值。

输出

第1行:1个整数,表示小小的距离

样例输入1 样例输出1
4 7
1 2 68
1 3 19
1 4 66
2 3 23
3 4 65
3 2 57
4 1 68
66

 

 

 

 

 

 

 

样例输入

样例输出
3 3
1 2 -7
2 3 4
3 1 2
No Solution

 

 

 

 

 

 

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node{
    int v,w,next;
}edge[500050];
int cnt,head[5050],n,m,dis[5050],tot[5050];
bool inq[5050];
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
bool SPFA()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    inq[1]=1;
    deque<int>q;
    q.push_front(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v,w=edge[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!inq[v])
                {
                    if(dis[v]<dis[u])q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                    if(++tot[v]>n)return 0;
                }
            }
        }
    }
    return 1;
}
int main()
{
    int u,v,w;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof head);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    SPFA()?printf("%dn",dis[n]):
    puts("No Solution");
}

 

SPAF:

标题陈说

有向图的单源点最短路线难题。起源编号为1,终点编号为n。

输入

第1行:2个空格分开的整数n(2<=n<=伍仟)和m(10<=m<=陆仟00),分别代表图的顶点数和边数。

第2..m+1行:每行3个空格分开的子弹头i,j, w。i表示一条边的源点,j表示终点, w代表权值。

输出

第1行:1个整数,表示小小的距离

样例输入1 样例输出1
4 7 1 2 68 1 3 19 1 4 66 2 3 23 3 4 65 3 2 57 4 1 68 66

 

 

 

 

 

样例输入

样例输出
3 3 1 2 -7 2 3 4 3 1 2 No Solution

 

 

 

 

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node{
    int v,w,next;
}edge[500050];
int cnt,head[5050],n,m,dis[5050],tot[5050];
bool inq[5050];
void addedge(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
bool SPFA()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    inq[1]=1;
    deque<int>q;
    q.push_front(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v,w=edge[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!inq[v])
                {
                    if(dis[v]<dis[u])q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                    if(++tot[v]>n)return 0;
                }
            }
        }
    }
    return 1;
}
int main()
{
    int u,v,w;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof head);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    SPFA()?printf("%dn",dis[n]):
    puts("No Solution");
}

 

Floyd:

代码:

#include<cstdio>  
#include<cstring>  
#define maxn 100  
#define INF -1  
int map[maxn][maxn];  
int n, m, path[maxn][maxn];  

void Floyd(int n)  
{  
    int i, j, k;  
    for(k = 0; k < n; ++k)  
        for(i = 0; i < n; ++i)  
            for(j = 0; j < n; ++j)  
                if(map[i][k] != INF && map[k][j] != INF && (map[i][k] + map[k][j] < map[i][j] || map[i][j] == INF)){  
                    map[i][j] = map[i][k] + map[k][j];  
                    path[i][j] = k;  
                }             
}  

void getPath(int v, int u)  
{  
    int k = path[v][u];  
    if(k == INF){  
        printf("%d===>", v);  
                return;  
    }  
    getPath(v, k);  
    getPath(k, u);  
}  

int main()  
{   
    scanf("%d%d", &n, &m);  
    memset(map, INF, sizeof(map));  
    memset(path, INF, sizeof(path));  
    int i, j, a, b, c;  
    for(i = 0; i < n; ++i) map[i][i] = 0;  
    for(i = 0; i < m; ++i){  
        scanf("%d%d%d", &a, &b, &c);  
        map[a][b] = c;  
    }  
    Floyd(n);  
    for(i = 0; i < n; ++i)  
        for(j = 0; j < n; ++j)  
            if(map[i][j] != INF){  
                printf("%d->%d:%dn the path is:", i, j, map[i][j]);  
                getPath(i, j);  
                printf("%dn", j);  
            }  
    return 0;  
}  

 

Floyd:

代码:

#include<cstdio>  
#include<cstring>  
#define maxn 100  
#define INF -1  
int map[maxn][maxn];  
int n, m, path[maxn][maxn];  

void Floyd(int n)  
{  
    int i, j, k;  
    for(k = 0; k < n; ++k)  
        for(i = 0; i < n; ++i)  
            for(j = 0; j < n; ++j)  
                if(map[i][k] != INF && map[k][j] != INF && (map[i][k] + map[k][j] < map[i][j] || map[i][j] == INF)){  
                    map[i][j] = map[i][k] + map[k][j];  
                    path[i][j] = k;  
                }             
}  

void getPath(int v, int u)  
{  
    int k = path[v][u];  
    if(k == INF){  
        printf("%d===>", v);  
                return;  
    }  
    getPath(v, k);  
    getPath(k, u);  
}  

int main()  
{   
    scanf("%d%d", &n, &m);  
    memset(map, INF, sizeof(map));  
    memset(path, INF, sizeof(path));  
    int i, j, a, b, c;  
    for(i = 0; i < n; ++i) map[i][i] = 0;  
    for(i = 0; i < m; ++i){  
        scanf("%d%d%d", &a, &b, &c);  
        map[a][b] = c;  
    }  
    Floyd(n);  
    for(i = 0; i < n; ++i)  
        for(j = 0; j < n; ++j)  
            if(map[i][j] != INF){  
                printf("%d->%d:%dn the path is:", i, j, map[i][j]);  
                getPath(i, j);  
                printf("%dn", j);  
            }  
    return 0;  
}  

 

BellmanFord:

难题陈诉

有向图负权的单源点最短路难题(贝尔manFord算法),要是最短路线有多条,输出路线经过边数非常的小的解; 即便最短路线边数一样,输出编号相当的小的种类.

输入

第1行:2个空格分开的整数n(2<=n<=500)和m(10<=m<=两千0),分别代表图的顶点数和边数。

第2..m+1行:每行3个空格分开的卡尺头i,j, w。i表示一条边的起源,j表示终点, w表示权值。

第m+2行:2个整数s,t(1<=s,t<=n),表示内定的终极。

输出

第1行:最小距离

第2行:最短路线(从源点到巅峰的队列,用1个空格分开)

只要出现负权回路,输出:No Solution

样例输入 样例输出
6 7
1 2 2
1 3 -1
2 4 -3
3 4 3
3 6 7
4 6 -2
3 5 6
1 6
-3
1 2 4 6

 

 

 

 

 

 

 

 

代码:

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
int f[20005][3],dis[505],s[505]; 
void print(int x)
{
    if(s[x]==0) return;
    print(s[x]);
    printf(" %d",x);
}
int main() 
{
    int n,m,i,j,q,z; 
    scanf("%d%d",&n,&m); 
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&f[i][0],&f[i][1],&f[i][2]); 
    scanf("%d%d",&q,&z);
    memset(dis,1,sizeof(dis)); 
    dis[q]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(dis[f[j][0]]+f[j][2]<dis[f[j][1]]&&i<n){
                dis[f[j][1]]=dis[f[j][0]]+f[j][2];
                s[f[j][1]]=f[j][0];
            }
            if(i==n&&dis[f[j][0]]+f[j][2]<dis[f[j][1]]){
                printf("No Solution");
                return 0;
            }
        }
    }
    printf("%dn",dis[z]); 
    printf("%d",q); 
    print(z);
}

 

Time:2017-02-03

BellmanFord:

主题材料陈述

有向图负权的单起点最短路难题(BellmanFord算法),假使最短路线有多条,输出路线经过边数很小的解; 如若最短路径边数同样,输出编号很小的种类.

输入

第1行:2个空格分开的整数n(2<=n<=500)和m(10<=m<=30000),分别代表图的顶点数和边数。

第2..m+1行:每行3个空格分开的卡尺头i,j, w。i表示一条边的源点,j表示终点, w代表权值。

第m+2行:2个整数s,t(1<=s,t<=n),表示钦点的极端。

输出

第1行:最小距离

第2行:最短路线(从起源到极点的类别,用1个空格分开)

万一出现负权回路,输出:No Solution

样例输入 样例输出
6 7
1 2 2
1 3 -1
2 4 -3
3 4 3
3 6 7
4 6 -2
3 5 6
1 6
-3
1 2 4 6

 

 

 

 

 

 

代码:

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
int f[20005][3],dis[505],s[505]; 
void print(int x)
{
    if(s[x]==0) return;
    print(s[x]);
    printf(" %d",x);
}
int main() 
{
    int n,m,i,j,q,z; 
    scanf("%d%d",&n,&m); 
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&f[i][0],&f[i][1],&f[i][2]); 
    scanf("%d%d",&q,&z);
    memset(dis,1,sizeof(dis)); 
    dis[q]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(dis[f[j][0]]+f[j][2]<dis[f[j][1]]&&i<n){
                dis[f[j][1]]=dis[f[j][0]]+f[j][2];
                s[f[j][1]]=f[j][0];
            }
            if(i==n&&dis[f[j][0]]+f[j][2]<dis[f[j][1]]){
                printf("No Solution");
                return 0;
            }
        }
    }
    printf("%dn",dis[z]); 
    printf("%d",q); 
    print(z);
}

 

Time:2017-02-03

] 最短路计算代码库,singularity代码库 【SinGuLaRiTy-1002】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved. Dijkstra: 题目描述 有向图的单起源...

编辑:关于计算机 本文来源:最短路计算代码库

关键词: