用Floyd算法求从某地到某地的最短路径(无向图)

#include
#include
using namespace std ;

#define MUNum 20
#define INFINITY 32767
#define Myprintf cout << "\n\t+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-\n" << endl

typedef struct PlaneGraph
{
int PathLength ;
char Pathname[20] ;
}PlaneGraph,PG[MUNum][MUNum] ;

typedef struct
{
char name[20] ;
int num ;
}infor ;

typedef struct
{
infor vexs[MUNum] ;
PG arcs ;
int vexnum ,arcnum ;
}AMGraph ;

void InitGraph(AMGraph &G)
{
int i ,j ;
cout << "\t请输入校园地点的数量、校园小径的个数:" ;
cin >> G.vexnum >> G.arcnum ;//点 边
Myprintf ;

for(i=0 ;i<G.vexnum ;i++)
    G.vexs[i].num = i ;//为点进行编号

cout << " 输入编号为(0-" << i << ")的校园地点的名称:\n\n" ;//店名称
for(i=0 ;i<G.vexnum ;i++)
{
    cout << "\t" ;
    cin  >> G.vexs[i].name ; 
}

cout << endl ;
Myprintf ;

for(i=0 ;i<G.vexnum ;i++)
    for(j=0 ;j<G.vexnum ;j++)
    {
        G.arcs[i][j].PathLength = INFINITY ; 
        strcpy(G.arcs[i][j].Pathname,"null");
    }

//输入路径信息
int v1,v2,w ;
char wn[20] ;
cout << "输入校园小径首尾地点编号、小径长度及小径名称\n\t(以-1 -1 -1 -1)结束输入:\n\t" << endl ;
cin  >> v1 >> v2 >> w >> wn ;
while(v1!=-1 && v2!=-1 && w!=-1 && strcmp(wn,"-1")!=0)
{
    cout << "\t" ;
    G.arcs[v1][v2].PathLength = w ;
    strcpy(G.arcs[v1][v2].Pathname,wn);
    G.arcs[v2][v1].PathLength = w ;
    strcpy(G.arcs[v2][v1].Pathname,wn);
    cin >> v1 >> v2 >> w >> wn ;
}

Myprintf ;

}

//Floyd
void ShortestPath(AMGraph G)
{
int v,u,i,j,w,k,flag=1;
int p[MUNum][MUNum][MUNum],D[MUNum][MUNum];
for(v=0 ; v for(w=0 ;w {
D[v][w] = G.arcs[v][w].PathLength;
for(u=0;u p[v][w][u] = 0 ;//
if(D[v][w] p[v][w][v] = p[v][w][w] = 1;//
}
for(u=0 ;u for(v=0 ;v for(w=0 ;w if(D[v][u]+D[u][w] {
D[v][w] = D[v][u]+D[u][w];
for(i=0;i p[v][w][i] = p[v][u][i] || p[u][w][i];//
}
while(flag)
{
cout cin >> k >> j ;
if(k=G.vexnum || j=G.vexnum )
{
cout << "该地点不存在!请重新输入!" << endl ;
Myprintf ;
}
else if(k == j )
{
cout << "始点和终点相同!请重新输入!" << endl ;

Myprintf ;
}
else
flag = 0 ;
}

    //输出信息
    int L[MUNum];
    L[0] = k;
    int l = 1 ;

    cout << "\t总路线长:" << D[k][j] << endl ;

    cout << G.vexs[k].name ;
    for(u=0 ;u<G.vexnum ;u++)
        if(p[k][j][u] && k!=u && j!=u)
        {
            cout << " ——> " << G.vexs[u].name ;
            L[l] = u ;
            l++ ;
        }   

    cout << " ——> " << G.vexs[j].name ;
    L[l] = j ;
    cout << endl ;

    cout << "\t路线:" ;
    for(u=0 ;u<l ;u++)
    {
        cout << G.arcs[L[u]] [L[u+1]].Pathname ;
        if(u != l-1)
            cout << " ——> " ;
    }
    cout << endl ;
    Myprintf ;

}

int main()
{
cout << "\n----------------------------------校园导航----------------------------------" << endl << endl ;
AMGraph G ;
InitGraph(G) ;
char k[10] ;
strcpy(k,"Yes");
while(strcmp(k,"Yes")==0)
{
ShortestPath(G);
cout << "请问是否继续?Yes or No?" << endl ;
cin >> k ;
if(strcmp(k,"Yes") != 0 )
cout << "\n----------------------------------停止查询----------------------------------" << endl ;
}
return 0 ;
}

数据:

10 10

大学生活动中心

敬文图书馆
实验楼
行知楼
防空洞
宿舍楼
办公楼
外国语学院
美术学院
体育馆

0 1 10 逸夫路
1 3 15 敬文路
4 3 70 达夫路
1 2 20 朝阳路
3 7 77 富康路
4 5 12 人民路
5 6 19 孚玉路
6 7 56 龙门路
8 9 73 纬七路
8 7 8 九江路
-1 -1 -1 -1

在路线输入:1 9 和 9 1的时候路线不一样,请问怎么解决

2个回答

http://blog.csdn.net/hackerain/article/details/6055946
#define MAX_VERTEX_NUM 20
#define MAX 1000000000
typedef struct
{
std::string vexs[MAX_VERTEX_NUM];
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];......
答案就在这里:Floyd算法求最短路径
----------------------你好,人类,我是来自CSDN星球的问答机器人小C,以上是依据我对问题的理解给出的答案,如果解决了你的问题,望采纳。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
floyd算法求任意两点最短路径,为什么输出的邻接矩阵总不正确
#include <iostream> using namespace std; #define MaxSize 100 #define INF 9999 class MGraph { public: void CreatMGraph(MGraph &); void ppath(int path[][100],int i,int j); void DisPath(int dist[][100],int path[][100],int n); void Floyd(MGraph G); void print(MGraph G); private: int edge[MaxSize][MaxSize]; char vertex[MaxSize]; int n,e; }; void MGraph::ppath(int path[][MaxSize],int i,int j) { int k; k=path[i][j]; if (k==-1) return; ppath(path,i,k); printf("%d,",k); ppath(path,k,j); } void MGraph::DisPath(int dist[][MaxSize],int path[][MaxSize],int n) { int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { cout<<"请输入需要查找的顶点:"; cin>>i>>j; if (dist[i][j]!=INF && i!=j) { printf(" 从%d到%d路径为:",i,j); printf("%d,",i); ppath(path,i,j); printf("%d",j); printf("\t最短路径长度为:%d\n",dist[i][j]); } } } } void MGraph::Floyd(MGraph G) { int i,j,k,dist[MaxSize][MaxSize]; int n=G.n; int path[MaxSize][MaxSize]; for(i=0;i<n;i++) for(j=0;j<n;j++) { dist[i][j]=G.edge[i][j]; path[i][j]=-1; } for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } DisPath(dist,path,n); } void MGraph::CreatMGraph(MGraph &G) { int i,j,k,w; int kind; int count=0; cout<<"请输入顶点数和边数:"; cin >> G.n >> G.e; cout<<"请输入边依附的顶点和权值:"<<endl; for(i=0;i<G.n;i++) { for(int j=0; j<G.n;j++) { G.edge[i][j] =INF; if(i==j) { G.edge[i][j]=0; } } } for(int k=0; k<G.e;k++) { cin >> i >> j >> w; G.edge[i][j] = w; if(kind==2) G.edge[j][i]=w; count++; } } void MGraph::print(MGraph G) { cout << "图的邻接矩阵为:" << endl; int i = 0; //打印行的标签 int j = 0; //打印列的标签 while (i!=G.n) { j= 0; while (j!=G.n) { if (G.edge[i][j] ==INF) cout << "∞" << " "; else cout << G.edge[i][j] << " "; j++; } cout << endl; i++; } } int main() { cout << "输入图的种类:1代表有向图,2代表无向图" << endl; int kind; cin >> kind; while (1) { if (kind == 1 || kind == 2) { break; } else { cout << "输入的图的种类编号不合法,请重新输入:1代表有向图,2代表无向图" << endl; cin >> kind; } } MGraph g; g.CreatMGraph(g); g. print(g); g.Floyd(g); printf("\n"); return 0; }
交通咨询问题:求任意两个顶点间最短路径,为什么无论输入哪两个顶点,都会显示无路径?
4.交通咨询系统 任务:设计一个简易交通咨询系统,能让旅客咨询从人一个城市到另一个城市之间的最短路径。 功能要求: (1)建立交通网络图的存储结构,并输出; (2)求单源最短路径(Dijkstra算法),并输出; (3)求任一对城市之间的最短路径,并输出。 第三个,无论我输入哪两个,都会显示无路径,这是为什么呢?求解 (ps:因为代码不是自己写的,所以想问问怎么解决)谢谢啦 ``` #include<stdio.h> #include<stdlib.h> #define MVNum 100 #define Maxint 0 typedef char VertexType; typedef int Adjmatrix; int D1[MVNum],P1[MVNum]; int D[MVNum][MVNum],P[MVNum][MVNum]; typedef enum {FALSE,TRUE}boolean; typedef struct{ VertexType vexs[MVNum] ; Adjmatrix arcs[MVNum][MVNum]; }MGraph; /*采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数*/ void CreateMGraph(MGraph *G,int n,int e) { int i,j,k,w; for(i=1;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint; printf("输入%d条边的i,j及w: \n",e); for(k=1;k<=e;k++) { scanf("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=G->arcs[j][i]=w; } printf("有向图的储存结构构建完毕!\n"); } /* 用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路经p[v] 以及其权D[v] 设G是有向向图的邻接矩阵,若 边<i,j> 不存在,则G[i][j]=Maxint S[v]为真当且仅当v属于S,即已求得从v1到v的最短路经 */ void Dijkstra(MGraph G,int v1,int n) { int D2[MVNum],P2[MVNum]; int v,i,w,min; boolean S[MVNum]; for(v=1;v<=n;v++) { S[v]=FALSE; D2[v]=G.arcs[v1][v]; if(D2[v]<Maxint) P2[v]=v1; else P2[v]=0; }//end_for D2[v1]=0; S[v1]=TRUE; //开始循环,每次求得v1到某个v顶点的最短路经,并将v加到S集总 for(i=2;i<n;i++) { min=Maxint; for(w=1;w<=n;w++) if(!S[w] && D2[w]<min) { v=w; min=D2[w]; } S[v]=TRUE; for(w=1;w<=n;w++) if(!S[w] && (D2[v]+G.arcs[v][w]<D2[w])) { //修改D2[w]和P2[w],w属于V-S D2[w]=D2[v]+G.arcs[v][w]; P2[w]=v; }//end_if }//end_for printf("路经长度 路经\n"); for(i=1;i<=n;i++) { printf("%5d",D2[i]); printf("%5d",i); v=P2[i]; while(v!=0) { printf("<-%d",v); v=P2[v]; } printf("\n"); } } /*弗洛伊德算法*/ void Floyd(MGraph G,int n) { int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(G.arcs[i][j]!=Maxint) P[i][j]=j; else P[i][j]=0; D[i][j]=G.arcs[i][j]; } //做k次迭代,每次迭代均试图将顶点k扩充到当前求得的从i到j的最短路经Pij上 for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; //修改长度 P[i][j]=P[i][k]; } } } } /*主函数*/ int main(void) { MGraph G; int n,e,v,w,k; int i,j; int xz=1; printf("输入图中顶点的个数和边数n,e:"); scanf("%d,%d",&n,&e); CreateMGraph(&G,n,e); printf("输出交通网络图的存储结构:\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d\t",G.arcs[i][j]); printf("\n"); } while(xz!=0) { printf("************求城市之间的最短路经************\n"); printf("============================================\n"); printf("1.求一个城市到所有城市的最短路经\n"); printf("2.求任意的两个城市之间的最短路经\n"); printf("============================================\n"); printf(" 请选择: 1 或 2 . 选择 0 退出 :"); scanf("%d",&xz); if(xz==2) { Floyd(G,n); printf("请输入源点(或称起点)和终点: V , W : "); scanf("%d,%d",&v,&w); k=P[v][w]; if(k==0) printf("顶点%d到%d无路经!\n",v,w); else { printf("从顶点%d到%d的最短路经是:%d",v,w,v); while(k!=w) { printf("->%d",k); k=P[k][w]; } printf("->%d\n",w); printf(" 路经长度:%d\n",D[v][w]); } } else if(xz==1) { printf("求单源路经,输入源点 v : "); scanf("%d",&v); Dijkstra(G,v,n); } } printf("结束求最短路经,再见!\n\n"); } ``` ![图片说明](https://img-ask.csdn.net/upload/201912/31/1577783926_868731.png)
求多个节点的最小生成图
求无向图两点之间最短路径可以用贪婪算法Dijkstra、动态规划Floyd、启发式算法A*等,但是求图中几个指定节点的最小生成树如何做呢?我查了很久没有查到相关资料,思考了很久也百思不得其解,哪位高手能指点迷津?
最短路径问题,迪杰斯特拉算法
``` #include<iostream> #include<iomanip> using namespace std; #define MAXINT 10000 /*无穷大*/ #define MVNUM 40 #define MAX 40 typedef struct { char *name; int num; char *introduction; }INFORMATION; typedef struct ACCESS { int length; }ACCESS,LENGTHA[MVNUM][MVNUM]; typedef struct { INFORMATION VEXS[MVNUM]; LENGTHA ARCS;// Maybe error int VEXNUM,ARCNUM; }AMGRAPH; AMGRAPH A;//全局变量 AMGRAPH CreatGraph() //初始化 { AMGRAPH G; int i, j; G.VEXNUM = 12; //14个顶点 G.ARCNUM = 16; //14条弧 for (i = 0; i<G.VEXNUM; i++) G.VEXS[i].num = i; //第i个景点的编号为i G.VEXS[0].name="26栋宿舍"; G.VEXS[1].name="二饭"; G.VEXS[2].name="泳池"; G.VEXS[3].name="网球场"; G.VEXS[4].name="沙地"; G.VEXS[5].name="旧场"; G.VEXS[6].name="新场"; G.VEXS[7].name="明德楼"; G.VEXS[8].name="图书馆"; G.VEXS[9].name="弘毅楼"; G.VEXS[10].name="天佑楼"; G.VEXS[11].name="艺悦楼"; G.VEXS[0].introduction="26栋宿舍位于学子路西侧,是计算机学院学生所住宿舍,万通超市上方。"; G.VEXS[1].introduction="第二学生饭堂位于学子路东侧,是学生好评最多的食堂。"; G.VEXS[2].introduction="北理工泳池位于学校后山半山腰上,对学生及社会人士都开放。"; G.VEXS[3].introduction="网球场位于学校东门附近,有4个场地供学生打网球。"; G.VEXS[4].introduction="沙地位于网球场西侧,以往学生在此举办各种活动,是一处聚会场地。"; G.VEXS[5].introduction="旧场位于网球场北侧,是北理珠最早的篮球场。"; G.VEXS[6].introduction="新场位于沙地西侧,是较新的篮球场。"; G.VEXS[7].introduction="明德楼位于学校中部,在夺命坡上方,是主要教学楼之一。"; G.VEXS[8].introduction="图书馆位于学校北门一侧,集图书馆、办公室、酒店于一体。"; G.VEXS[9].introduction="弘毅楼位于学校新大门对面,是主要教学楼之一。"; G.VEXS[10].introduction="天佑楼位于弘毅楼西侧,是航空学院的主教学楼。"; G.VEXS[11].introduction="艺悦楼位于天佑楼西侧,是设计与艺术学院的主教学楼。"; for (i = 0; i<G.VEXNUM; i++) for (j = 0; j<G.VEXNUM; j++) G.ARCS[i][j].length = MAXINT; G.ARCS[0][1].length=20; G.ARCS[0][2].length=100; G.ARCS[0][3].length=280; G.ARCS[1][3].length=280; G.ARCS[1][4].length=110; G.ARCS[1][7].length=210; G.ARCS[2][7].length=130; G.ARCS[1][9].length=280; G.ARCS[3][4].length=20; G.ARCS[3][5].length=5; G.ARCS[4][6].length=5; G.ARCS[5][8].length=35; G.ARCS[6][8].length=50; G.ARCS[7][9].length=80; G.ARCS[8][9].length=200; G.ARCS[9][10].length=40; G.ARCS[10][11].length=20; for (i=0;i<G.VEXNUM;i++) for (j=0;j<G.VEXNUM;j++) G.ARCS[j][i].length = G.ARCS[i][j].length; //无向网 return G; } void SHORTESTPATH_DIJ(AMGRAPH *G) {//DIJ算法,计算最短路径 int V,min,i,j,w,k=0,V0,f=1,t; int D[32],PATH[32][32]; bool S[32]; while (f) { cout<<"请输入一个起始景点编号:"; cin>>V0; //输入一个值赋给V0 if (V0<0 || V0>G->VEXNUM) { cout<<"景点编号不存在!请重新输入景点编号:"; cin>>V0; } if (V0 >=0 && V0<G->VEXNUM) f=0; } for(V=0;V<G->VEXNUM;V++) { S[V]=false; D[V]=G->ARCS[V0][V].length; for(w=0;w<G->VEXNUM;w++) { PATH[V][w]=0; } if(D[V]<MAXINT) { PATH[V][V0]=1; PATH[V][V]=1; } } D[V0]=0; S[V0]=true; for(i=1;i<G->VEXNUM;i++) { min=MAXINT; for(w=0;w<G->VEXNUM;w++) { if(!S[w]&&D[w]<min) { V=w; min=D[w]; } } S[V]=true; for(w=0;w<G->VEXNUM;w++) { if(!S[w] && (min+G->ARCS[V][w].length<D[w])) { D[w]=min+G->ARCS[V][w].length; for(j=0;j<G->VEXNUM;j++) PATH[w][j]=PATH[V][j]; PATH[w][w]=1; } } } for(V=0;V<G->VEXNUM;V++) { t=0; if(V0!=V) printf("%s",G->VEXS[V0].name); for(w=0;w<G->VEXNUM;w++) { if(PATH[V][w]!=0 && w!=V0) { printf("-%s",G->VEXS[w].name); if(w==5||w==6) { t=1; } } k++; } if(V0!=V&&(V0==5||V0==6||t==1)) { cout<<"\t此路段部分需步行!"; t=0; } if(k>G->VEXNUM-1 && V0!=V) printf("\t路程:%dm\n\n",D[V]); } } void SHORTESTPATH_FLOYD(AMGRAPH G) {//FLOYD算法计算各对顶点之间的最短路径 int D[32][32],PATH[32][32]; int i,j,k; for(i=0;i<G.VEXNUM;i++) for(j=0;j<G.VEXNUM;i++) { D[i][j]=G.ARCS[i][j].length; if(D[i][j]<MAXINT) PATH[i][j]=i; else PATH[i][j]=-1; } for(k=0;k<G.VEXNUM;k++) for(i=0;i<G.VEXNUM;i++) for(j=0;j<G.VEXNUM;j++) { if(D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; PATH[i][j]=PATH[k][j]; } } } void printjuzhen(AMGRAPH G) { int i,j,W=0; cout<<"图的邻接矩阵:"<<endl; for(i=0;i<G.VEXNUM;i++) { for(j=0;j<G.VEXNUM;j++) { if(G.ARCS[i][j].length==MAXINT) { cout<<setw(6)<<"∞"; } else cout<<setw(6)<<G.ARCS[i][j].length; W++; if(W%G.VEXNUM==0) cout<<endl; } } } void main() { A=CreatGraph(); SHORTESTPATH_DIJ(&A); printjuzhen(A); } ``` ![图片说明](https://img-ask.csdn.net/upload/201612/24/1482560926_949494.jpg) ![图片说明](https://img-ask.csdn.net/upload/201612/24/1482560938_648604.jpg) 请问怎么可以正确地打印最近的路,而不是按照地点的数字顺序打印出错误的线路。
新手 C语言 Floyd算法 怎么递归写路径追溯
``` #include <stdio.h> #include <math.h> #define MAXSIZE 100 #define Infinity 10001 int G[MAXSIZE][MAXSIZE],Nv,Ne,Distance,x[MAXSIZE],y[MAXSIZE],path[MAXSIZE][MAXSIZE],FirstPoint[MAXSIZE],count=0,count_2=0,Destination[MAXSIZE],D[MAXSIZE][MAXSIZE]; int GetDistance(int Xa,int Ya,int Xb,int Yb) { return (int)pow((pow(Xa-Xb,2)+pow(Ya-Yb,2)),0.5); } void PrintPath(int i,int j) { } void BuildGraph() { int i,j; scanf("%d %d", &Nv,&Distance); if(Distance+7.5>=50) { printf("1\n"); return ; } for (i = 0; i<Nv; i++) { scanf("%d %d",&x[i],&y[i]); if(GetDistance(x[i],y[i],0,0)<=7.5+Distance) { FirstPoint[count]=i; count++; } if(!(abs(x[i])<50-Distance&&abs(y[i])<50-Distance)) { Destination[count_2]=i; count_2++; } } for (i = 0; i<Nv; i++) { for (j = 0; j<Nv; j++) { if(GetDistance(x[i],y[i],x[j],y[j])<=Distance&&i!=j) { G[i][j]=1; G[j][i]=1; } else if(i==j) { G[i][j]=0; } else { G[i][j]=Infinity; G[j][i]=Infinity; } } } } void FindPath() { int i,j,k,MinDist=Infinity,Temp_i,Temp_j; for(i=0;i<Nv;i++) { for(j=0;j<Nv;j++) { D[i][j]=G[i][j]; path[i][j]=-1; } } for(k=0;k<Nv;k++) { for(i=0;i<Nv;i++) { for(j=0;j<Nv;j++) { if(D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } } } for(i=0;i<count;i++) { for(j=0;j<count_2;j++) { if(D[FirstPoint[i]][Destination[j]]<MinDist) { MinDist=D[FirstPoint[i]][Destination[j]]; Temp_i=FirstPoint[i]; Temp_j=Destination[j]; } } } if(MinDist==Infinity) { printf("0\n"); } else { printf("%d\n",D[Temp_i][Temp_j]+2); PrintPath(Temp_i,Temp_j); } } int main() { BuildGraph(); FindPath(); return 0; } ``` 请问如何用递归的方法写出PrintPath这个函数? 测试数据 输入 17 15 10 -21 10 21 -40 10 30 -50 20 40 35 10 0 -10 -25 22 40 -40 -30 30 -10 22 0 11 25 21 25 10 10 10 10 35 -30 10 输出 4 0 11 10 21 10 35 原题链接:https://pta.patest.cn/pta/test/1342/exam/4/question/23159 代码写的比较乱 不好意思
求救贴 女大学生卡死在学校oj题上 求助求助 Floyd-Warshall算法
## **题目** ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- Description Floyd-Warshall算法是求一个图中任意两点之间的最短路径长度的算法。 给出一个有向图,请计算图中任意两个顶点之间的最短路径,及其长度。 Input 单测试用例。 第一行是该有向图的 顶点数n ( 0 < n < 500 )(注:图有n个顶点,首个顶点的编号是0。 ) 第二行是该有向图的 边数e ( 0 < e < n×n ) 接下来e行,每行三个整数 i 、j 和 k,表示 顶点i 到顶点j 有一条弧,长度为k。 ( 0 ≤ i, j < n ) (注:输入数据中不含 自环 。) 接下来一个正整数Q,表示有Q个询问。 接下来Q行,每行两个非负整数u和v,表示询问 顶点u 到 顶点v 的最短路长度,以及该最短路径是怎么走的。 Output 对每个询问输出三行。 第一行是一个整数,表示顶点u到顶点v的最短路长度。如果不可达,输出INF ,且不用输出第二行。如果路径长度为0,也不用输出第二行。 第二行是若干个整数,每个整数后面跟一个空格,表示顶点u 到顶点v 的最短路的顶点序列。 第三行是一个空行,仅起分隔作用。 Sample Input 3 5 0 1 4 0 2 11 1 0 6 1 2 2 2 0 3 3 0 2 0 1 1 0 Sample Output 6 0 1 2 4 0 1 5 1 2 0 Hint 样例如下图所示 1397_1.png 注意:本题是special judge,但validator没有写得很完美。你的代码输出时如果没有间隔的空行,PE会判为WA ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以下是本人的代码 #include<stdio.h> #include<stdlib.h> #define MAX 505 typedef struct { int edges[MAX][MAX]; int n,e; }MGraph; MGraph G; int D[MAX][MAX],path[MAX][MAX]; int inf=99999999; void Path(int u,int v) { int k; k=path[u][v]; if(k==-1) return ; Path(u,k); printf("%d ",k); Path(k,v); } void Dispath(int u,int v) { if(D[u][v]==inf||D[u][v]==0) { printf("INF\n"); } else { printf("%d\n",D[u][v]); printf("%d ",u); Path(u,v); printf("%d\n",v); } } void Floyd(MGraph G) { int Q,u,v; int i,j,k; for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) { D[i][j]=G.edges[i][j]; path[i][j]=-1; } } /*for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",D[i][j]); printf("\n"); } printf("\n");*/ for(k=0;k<G.n;k++) { for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) if(D[i][k]<inf&&D[k][j]<inf&&D[i][j]>(D[i][k]+D[k][j])) { D[i][j]=D[i][k]+D[k][j]; //printf("%d ",D[i][j]); path[i][j]=k; }} } /*for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",D[i][j]); printf("\n"); } printf("\n"); for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",path[i][j]); printf("\n"); } system("pause");*/ scanf("%d",&Q); for(i=0;i<Q;i++) { scanf("%d %d",&u,&v); Dispath(u,v); printf("\n"); } } int main() { int i,j,k,t; scanf("%d",&G.n); scanf("%d",&G.e); for(i=0;i<G.n;i++)/////////////ÁÚ½Ó¾ØÕó³õʼ»¯ for(j=0;j<G.n;j++) { if(i==j) G.edges[i][j]=0; else G.edges[i][j]=inf; //printf("%d ",G.edges[i][j]); } //printf("\n"); //printf("%d",G.e); //printf("%d\n",INF); for(t=0;t<G.e;t++) { //system("pause"); scanf("%d %d %d",&i,&j,&k); G.edges[i][j]=k; } /*for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",G.edges[i][j]); printf("\n"); } printf("\n");*/ //printf("text\n"); Floyd(G); return 0; }
问一个Floyd(弗洛伊德)最短距离算法问题???
dp[j][k]= min{ dp[k][k-1]+ dp[k][j][k-1] } 对于这行代码每次验证一个顶点,当验证完第一个顶点完后,接着再验证第二个顶点,第三个顶点直到k=n结束,但我有一个疑惑,当验证第二的的时候这时候,我回过头看了下这里的k(顶点)在被验证时的先后顺序好像并没什么影响,不知道是怎么证明出来的????
我有一个数据结构最短路径程序,求解释里边程序每个步骤的意思
#include <iostream> #include <string> #define INFINITY 30000 //定义很大的数 #define MAX_VERTEX_NUM 20//最大的边数 using namespace std; typedef struct{ string vexs[18]; int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 int vexnum,arcnum;//图的当前定点数和边数 }Graph; void CreateUDN(Graph &G)//创建无向图 { int i,j; G.vexnum = 17; G.arcnum = 21; //初始化各个顶点的信息 G.vexs[1] ="入口"; G.vexs[2] ="人工湖"; G.vexs[3] ="后勤"; G.vexs[4] ="塑胶操场"; G.vexs[5] ="小广场"; G.vexs[6] ="12号楼"; G.vexs[7] ="13号楼"; G.vexs[8] ="学府公寓"; G.vexs[9] ="8号楼"; G.vexs[10] ="三教"; G.vexs[11] ="一教"; G.vexs[12] ="风雨操场"; G.vexs[13] ="第一餐厅"; G.vexs[14] ="排球场"; G.vexs[15] ="图书馆"; G.vexs[16] ="邮局"; G.vexs[17] ="二办"; //初始化存在边的权值 for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) G.arcs[i][j]=INFINITY; G.arcs[0][1]=G.arcs[1][0]=20; G.arcs[0][4]=G.arcs[4][0]=20; G.arcs[1][2]=G.arcs[2][1]=30; G.arcs[2][3]=G.arcs[3][2]=20; G.arcs[2][5]=G.arcs[5][2]=30; G.arcs[4][5]=G.arcs[5][4]=10; G.arcs[5][6]=G.arcs[6][5]=20; G.arcs[5][7]=G.arcs[7][5]=50; G.arcs[6][7]=G.arcs[7][6]=40; G.arcs[6][8]=G.arcs[8][6]=10; G.arcs[7][9]=G.arcs[9][7]=20; G.arcs[7][10]=G.arcs[10][7]=20; G.arcs[8][9]=G.arcs[9][8]=20; G.arcs[8][13]=G.arcs[13][8]=30; G.arcs[9][10]=G.arcs[10][9]=20; G.arcs[10][11]=G.arcs[11][10]=20; G.arcs[11][12]=G.arcs[12][11]=10; G.arcs[12][15]=G.arcs[15][12]=20; G.arcs[13][14]=G.arcs[14][13]=20; G.arcs[14][15]=G.arcs[15][14]=20; G.arcs[15][16]=G.arcs[16][15]=40; } //计算最短路径 void ShortestPath_FLOYD(Graph G,int D[17][17],int P[17][17]) { int u,v,i,j,w; for ( i=0; i<17; ++i) for ( j=0; j<17; ++j) { D[i][j]=G.arcs[i][j];//初始化 P[i][j]= -1;//初始化 } for( u=0; u<17; u++) for (v=0; v<17; v++) for ( w=0; w<17; w++) if (D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; P[v][w]=u;//u为v到w最短路径上的前驱 } } //输出最短路径上经过的点 void ppath(Graph G,int path[17][17],int i,int j) { int k; k=path[i][j]; if(k==-1) return; ppath(G,path,i,k); cout<<G.vexs[k+1]; cout<<"->"; ppath(G,path,k,j); } int main() { Graph G; CreateUDN(G); while(1) { cout<<"*****欢迎使用校园导航系统*****"<<endl; cout<<"* 1.查看地图 *"<<endl; cout<<"* 2.查询地点信息 *"<<endl; cout<<"* 3.问路系统 *"<<endl; cout<<"* 4.退出系统 *"<<endl; cout<<"******************************"<<endl; int choose; cin>>choose; if(choose == 1) { cout<<"17|"<<endl; cout<<"16|------13"<<endl; cout<<"15| 12|"<<endl; cout<<"14| 11|------8__ |4"<<endl; cout<<" | 10|------| | |" <<endl; cout<<" |______9|______7__|6______|3"<<endl; cout<<" | | "<<endl; cout<<" |5 | "<<endl; cout<<" | __2| "<<endl; cout<<" | _| "<<endl; cout<<" 1_| "<<endl; } if(choose == 2) { int num; cout<<"请输入想要查询地点的编号: "; cin>>num; cout<<G.vexs[num]; cout<<endl; } if(choose == 3) { int v,w; int D[17][17]; int P[17][17]; ShortestPath_FLOYD(G, D, P); cout<<"请输入出发点和目的地的编号:"; cin>>v>>w; cout<<"“"; cout<<G.vexs[v]; cout<<"”到“"; cout<<G.vexs[w]; cout<<"”的最短路线长为"<<D[v-1][w-1]<<endl; cout<<"为:"; cout<<G.vexs[v]; cout<<"->"; ppath(G,P,v-1,w-1); cout<<G.vexs[w]; cout<<endl; } if(choose == 4) break; } return 0; }
关于指针和引用的问题?
``` #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; /* 构件图 */ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges=16; G->numVertexes=9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { G->vexs[i]=i; } for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < G->numVertexes; j++) { if (i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } G->arc[0][1]=1; G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3; G->arc[4][6]=6; G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7; G->arc[7][8]=4; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /* Floyd算法,求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ void ShortestPath_Floyd(MGraph G, Patharc &P, ShortPathTable *D) { int v,w,k; for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */ { for(w=0; w<G.numVertexes; ++w) { (*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */ P[v][w]=w; /* 初始化P */ } } for(k=0; k<G.numVertexes; ++k) { for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { if ((D)[v][w]>(*D)[v][k]+(*D)[k][w]) {/* 如果经过下标为k顶点路径比原两点间路径更短 */ (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */ p[v][w]=P[v][k];/* 路径设置为经过下标为k的顶点 */ } } } } } int main(void) { int v,w,k; MGraph G; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ CreateMGraph(&G); ShortestPath_Floyd(G,P,&D); printf("各顶点间最短路径如下:\n"); for(v=0; v<G.numVertexes; ++v) { for(w=v+1; w<G.numVertexes; w++) { printf("v%d-v%d weight: %d ",v,w,D[v][w]); k=P[v][w]; /* 获得第一个路径顶点下标 */ printf(" path: %d",v); /* 打印源点 */ while(k!=w) /* 如果路径顶点下标不是终点 */ { printf(" -> %d",k); /* 打印路径顶点 */ k=P[k][w]; /* 获得下一个路径顶点下标 */ } printf(" -> %d\n",w); /* 打印终点 */ } printf("\n"); } printf("最短路径D\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d\t",D[v][w]); } printf("\n"); } printf("最短路径P\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d ",P[v][w]); } printf("\n"); } return 0; } _****_ ```
(*D)[v][w]为何要加上*,不加*程序可以运行但是会出错这是为什么?
![图片说明](https://img-ask.csdn.net/upload/201909/14/1568467927_949056.png) ``` #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; /* 构件图 */ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges=16; G->numVertexes=9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { G->vexs[i]=i; } for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < G->numVertexes; j++) { if (i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } G->arc[0][1]=1; G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3; G->arc[4][6]=6; G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7; G->arc[7][8]=4; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /* Floyd算法,求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) { int v,w,k; for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */ { for(w=0; w<G.numVertexes; ++w) { (*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */ (*P)[v][w]=w; /* 初始化P */ } } for(k=0; k<G.numVertexes; ++k) { for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w]) {/* 如果经过下标为k顶点路径比原两点间路径更短 */ (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */ (*P)[v][w]=(*P)[v][k];/* 路径设置为经过下标为k的顶点 */ } } } } } int main(void) { int v,w,k; MGraph G; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ CreateMGraph(&G); ShortestPath_Floyd(G,&P,&D); printf("各顶点间最短路径如下:\n"); for(v=0; v<G.numVertexes; ++v) { for(w=v+1; w<G.numVertexes; w++) { printf("v%d-v%d weight: %d ",v,w,D[v][w]); k=P[v][w]; /* 获得第一个路径顶点下标 */ printf(" path: %d",v); /* 打印源点 */ while(k!=w) /* 如果路径顶点下标不是终点 */ { printf(" -> %d",k); /* 打印路径顶点 */ k=P[k][w]; /* 获得下一个路径顶点下标 */ } printf(" -> %d\n",w); /* 打印终点 */ } printf("\n"); } printf("最短路径D\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d\t",D[v][w]); } printf("\n"); } printf("最短路径P\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d ",P[v][w]); } printf("\n"); } return 0; } ```
程序都运行完了才中断,定位到if (!has_cctor)
如题,我写了一些图的算法,prim、Floyd什么的,有delete的代码,都运行完了没有问题,直到最后system("pause")之后才发生中断跳到 exe_common.inl 的如下代码里 if (!__scrt_is_managed_app()) exit(main_result); 大家知道为啥嘛
Dijkstra Or Floyd Or dfs
Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗? Input 输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。 Output 对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间 Sample Input 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 Sample Output 3 2
求求。怎么在里面插入拓补排序。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; int n = 0; int a[100][100]; int menu() { int m; printf(" 求最小生成树\n"); printf(" ________________________________\n\n"); printf(" 1 输入城市之间的信息\n"); printf(" 2 判断是否能构成一个最小生成树\n"); printf(" 3 查询信息\n"); printf(" 4 退出\n"); printf(" ________________________________\n\n"); printf(" 请输入所选功能1--4\n"); scanf("%d",&m); return m; } void xin_input() { printf("1 遍历所有城市的最小生成树\n"); printf("2 查询两个城市之间的距离\n"); printf("3 退出\n"); //printf("________________________________\n\n"); } //以下为克鲁斯卡尔算法 typedef struct node //构造一个结构体,两个城市可以看成起点和终点,之间的路道可以看成一个边 { int st; //起点 int ed; //终点 int dis;//距离 }node; node p[1000]; int pre[1000],rank[1000]; bool cmp(node p1,node p2) { return p1.dis < p2.dis; } //下面三个函数是并查集,其作用是检验当一条边添加进去,是否会产生回路 void set(int x) { pre[x] = x;//初始化 rank[x] = 0; } int find(int x)//找到这个点的祖先 { if(x != pre[x]) pre[x] = find(pre[x]); return pre[x]; } void Union(int x,int y)//将这两个添加到一个集合里去 { x = find(x); y = find(y); if(rank[x] >= rank[y]) { pre[y] = x; rank[x] ++; } else pre[y] = x; } void Kruskal() // { int ans = 0,i,j,k = 0; for(i = 1;i <= n;i ++) set(i); for(i = 1;i <= n;i ++) for(j = i + 1;j <= n;j ++) { p[++k].st = i; p[k].ed = j; p[k].dis = a[i][j]; //先把所有城市之间的路段看成一个边 } sort(p + 1,p + k + 1,cmp);//把所有的边按从小到大进行排序 int count = 0; for(i = 1;i <= k;i ++) { if(find(p[i].st) != find(p[i].ed))//如果这两点连接在一起不构成一个回路,则执行下面操作 { printf("第%d条路段为:%d--%d,权值为%d\n",++ count,p[i].st,p[i].ed,p[i].dis);//将这条边的起点、终点打印出来 ans += p[i].dis; //说明这条路段要用 Union(p[i].st,p[i].ed); } } printf("遍历所有城市的最短路程为: %d\n",ans);//最短遍历的路程 //printf("________________________________\n"); } //普里姆算法 int prim() { int close[100],low[100],i,j,ans = 0;//close[j]表示离j最近的顶点,low[j]表示离j最短的距离 bool use[100]; use[1] = 1; for(i = 2;i <= n;i ++) { low[i] = a[1][i]; //初始化 close[i] = 1; use[i] = 0; } for(i = 1;i < n;i ++) { int min = 100000000,k = 0; for(j = 2;j <= n;j ++) { if(use[j] == 0 && min > low[j])//找到最小的low[]值,并记录 { min = low[j]; k = j; } } //printf("%d %d\n",close[k],k); for(j = 2;j <= n;j ++) { if(use[j] == 0 && low[j] > a[k][j]) { low[j] = a[k][j]; //修改low[]值和close[]值 close[j] = k; } } ans += a[close[k]][k]; } return ans; } //求最短路径-单源点到其余点的最短路径(Dijkstra算法) void ShortestPath_DIJ(int x,int y) //X指单源点,y指目标点 { int i,d[100],j; bool use[100]; for(i = 1;i <= n;i ++) { use[i] = 0; //初始化 d[i] = a[x][i]; } use[x] = 1;//这个点肯定用过 d[x] = 0; for(i = 1;i < n;i ++)//执行n-1次操作 { int min = 100000000,v; for(j = 1;j <= n;j ++) { if(use[j] == 0 && min > d[j])//找出最短距离的 { min = d[j]; v = j; } } use[v] = 1; for(j = 1;j <= n;j ++) { if(use[j] == 0 && d[j] > min + a[v][j])//修改d[]的值 { d[j] = min + a[v][j]; } } } printf("%d城市到城市%d的最短距离为: %d\n",x,y,d[y]); } //求每一对顶点之间的最短路径(Floyd算法) int b[100][100]; void ShortestPath_FLOYD() //这个算法耗时多(n^3),不过容易理解 { int i,j,k; for(i = 1;i <= n;i ++) for(j = 1;j <= n;j ++) b[i][j] = a[i][j]; //先b[][]进行保存,避免a[][]的值发生变化 for(k = 1;k <= n;k ++) for(i = 1;i <= n;i ++) for(j = 1;j <= n;j ++) if(b[i][j] > b[i][k] + b[k][j]) b[i][j] = b[i][k] + b[k][j]; while(1) { int st,ed; printf("请输入两个城市的编号:\n");//对此进行多次操作 scanf("%d%d",&st,&ed); printf("%d 城市到 %d 城市的最短距离为: %d\n",st,ed,b[st][ed]); //printf("________________________________\n"); char str[100]; printf("是否要继续? yes or no\n"); scanf("%s",str); if(strcmp(str,"no") == 0) { //printf("________________________________\n"); break; } } } void shuru()//输入城市信息 { int i,j; if(n != 0) { char str[100]; printf("是否要确定输入新的城市之间的信息? yes or no ?\n"); scanf("%s",str); if(strcmp(str,"no") == 0) { return ; } } printf("请输入城市的个数:\n"); scanf("%d",&n); printf("输入%d个城市的邻接矩阵:\n",n); for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) scanf("%d",&a[i][j]); } //printf("________________________________\n"); } void chaxun() //一个查徇两个城市最短径的操作 { while(1) { int t1,t2; printf("输入第一个城市的编号:\n"); scanf("%d",&t1); printf("输入第二个城市的编号:\n"); scanf("%d",&t2); ShortestPath_DIJ(t1,t2);//调用 char str[100]; printf("是否要继续? yes or no\n"); scanf("%s",str); if(strcmp(str,"no") == 0) { //printf("________________________________\n"); break; } } } void chaxun_func() { if(n == 0) { printf("这里没有城市之间的信息\n"); return; } xin_input(); printf("请选择以上功能:1-3\n"); int m1; scanf("%d",&m1); printf("\n"); if(m1 == 1) Kruskal(); else if(m1 == 2) { chaxun(); } //else // break; } void judge() { int ans; ans = prim(); if(ans >= 100000000) printf("不能构成最小生成树\n"); else printf("能构成最小生成树\n"); } int main() { while(1) { switch(menu()) { case 1:shuru();break; case 2:judge();break; case 3: chaxun_func();break; case 4:goto loop; } } loop:; return 0; }
c语言实现的套汇问题 钱的种类多了就就不行了
不知道为什么 第四种货币之后就不行了! #include<stdio.h> #define MAX 2000 #define MIN 0 int n; int Path[MAX][MAX]; float value[MAX][MAX]; typedef struct{ int vexs[MAX]; //顶点向量 可以存储每个顶点的信息 float arc[MAX][MAX];//邻接矩阵 主要存放关于边的信息 int vexnum,arcnum; //图中当前顶点数和弧数 }MGraph; void CreateDG(MGraph *G) { int i,j; float A[10][10]={ {1.0,65.2,109.4,7.0,0.8,0.7,29.2,1.2,31.4,1.2}, {0.015,1.0,1.6,0.1,0.012,0.011,0.45,0.019,0.48,0.02}, {0.009,0.6,1.0,0.05,0.007,0.007,0.27,0.01,0.28,0.01}, {0.14,9.3,17.1,1.0,0.13,0.12,4.7,0.2,4.5,0.2}, {1.2,80.3,127.6,7.8,1.0,0.87,34.9,1.5,38.7,1.55}, {1.3,89.8,145.5,9.2,1.1,1.0,39.8,1.7,43.2,1.75}, {0.14,2.2,3.6,0.2,0.03,0.025,1.0,0.04,1.1,0.044}, {0.8,50.5,86.5,5.1,0.7,0.6,23.7,1.0,24.3,1.01}, {0.03,2.1,3.5,0.22,0.025,0.023,0.9,0.04,1.0,0.04}, {0.76,50.6,82.6,4.8,0.64,0.5,22.6,0.98,24.3,1.0}}; printf("1--------美元\n2--------印度卢比\n3--------日元\n "); G->vexnum=10; G->arcnum=G->vexnum* (G->vexnum-1); for(i=1;i<=G->vexnum;i++) { G->vexs[i]=i; } for(i=1;i<=G->vexnum;i++) { for(j=1;j<=G->vexnum;j++) { G->arc[i][j]=A[i-1][j-1]; } } } void ShortestPath_FLOYD(MGraph *G) { int i,j,k; for(i=1;i<=G->vexnum;i++) { for(j=1;j<=G->vexnum;j++) { if(i==j) value[i][j] = 1; else value[i][j]=G->arc[i][j]; if(G->arc[i][j]>MIN) Path[i][j]=i; else Path[i][j]=0; } } for(k=1;k<=G->vexnum;k++) {for(i=1;i<=G->vexnum;i++) { for(j=1;j<=G->vexnum;j++) { if(value[i][k]*value[k][j]>value[i][j]) { value[i][j]=value[i][k]*value[k][j]; Path[i][j]=Path[k][j]; } } } } } void Procedure_print(int i,int j){ int a; if(Path[i][j]==i) { printf("%d",i); return; } else if(Path[i][j]==0)//输出结点i与结点j之间不存在通路 printf("NO path"); else { printf("%d ",Path[i][j]); /* a++; if(a == 1) { return ; } */ Procedure_print(i,Path[i][j]); } } int main() { int i,j; MGraph G; CreateDG(&G); ShortestPath_FLOYD(&G); for(int k=1;k<=10;k=k+1) { scanf("%d",&i); if(value[i][i]>1) { printf("请输入开始币种\n"); printf("套汇所得为:"); printf("%f\n",value[i][i]); printf("兑换顺序的逆序输出:\n%d ",i); Procedure_print(i,i); printf("\n"); } else { printf("wrong\n"); } } }
引发了未经处理的异常:读取访问权限冲突。 this->**matrix** 是 0xCDDDCDDE。
# 可从后往前看,来自学生党的求助,缺的都是iostream ## #include "pch.h", ## #include "Graph.h" Edge::Edge() { from = -1; to = -1; weight = 0; } Edge::Edge(int f, int t, int w) { from = f; to = t; weight = w; } Graph::Graph() { } Graph::Graph(int numVert) { numVertex = numVert; numEdge = 0; Indegree = new int[numVertex]; Mark = new int[numVertex]; for (int i = 0; i < numVertex; i++) { Mark[i] = UNVISITED; Indegree[i] = 0; } } Graph::~Graph() { delete[] Mark; delete[] Indegree; } bool Graph::IsEdge(Edge oneEdge) { if (oneEdge.weight > 0 && oneEdge.weight < INFINITYS && oneEdge.to >= 0) return true; else return false; } void Graph::clearVisitedMark() { for (int i = 0; i < numVertex; i++) Mark[i] = UNVISITED; } #pragma once #include <iostream> using namespace std; #define MAX 102 #define INFINITYS 65536 #define UNVISITED 0 #define VISITED 1 #ifndef GRAPH_H #define GRAPH_H class Edge { public: Edge(); Edge(int f, int t, int w); ~Edge() {} bool operator < (const Edge &arg) { return (this->weight < arg.weight); } bool operator == (const Edge &arg) { return (this->weight == arg.weight); } bool operator > (const Edge &arg) { return (this->weight > arg.weight); } bool operator <= (const Edge &arg) { return (this->weight <= arg.weight); } bool operator >= (const Edge &arg) { return (this->weight >= arg.weight); } int from; int to; int weight; }; class Graph { public: Graph(); Graph(int numVert); virtual ~Graph(); int VerticesNum() { return numVertex; } int EdgesNum() { return numEdge; } bool IsEdge(Edge oneEdge); int FromVertex(Edge oneEdge) { return oneEdge.from; } int ToVertex(Edge oneEdge) { return oneEdge.to; } int Weight(Edge oneEdge) { return oneEdge.weight; } void clearVisitedMark(); /*virtual Edge FirstEdge(int oneVertex) = 0; virtual Edge NextEdge(Edge preEdge) = 0; virtual void setEdge(int from, int to, int weight) = 0; virtual void delEdge(int from, int to) = 0;*/ protected: int numVertex; int numEdge; int * Mark; int * Indegree; }; #endif // !GRAPH_H #include "pch.h" #include "Graphm.h" Graphm::Graphm() { } Graphm::~Graphm() { for (int i = 0; i < numVertex; i++) delete[] matrix[i]; delete[] matrix; } Edge Graphm::FristEdge(int oneVertex) { Edge myEdge; myEdge.from = oneVertex; for (int i = 0; i < numVertex; i++) if (matrix[oneVertex][i] != 0 && matrix[oneVertex][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[oneVertex][i]; break; } return myEdge; } Edge Graphm::NextEdge(Edge preEdge) { Edge myEdge; myEdge.from = preEdge.from; if (preEdge.to < numVertex) for (int i = preEdge.to + 1; i < numVertex; i++) if (matrix[preEdge.from][i] != 0 && matrix[preEdge.from][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[preEdge.from][i]; break; } return myEdge; } void Graphm::setEdge(int from, int to, int weight) { if (matrix[from][to] <= 0) { numEdge++; Indegree[to]++; } matrix[from][to] = weight; } void Graphm::delEdge(int from, int to) { if (matrix[from][to] > 0) { numEdge--; Indegree[to]--; } matrix[from][to] = 0; } void Graphm::InitWith2DimArray(int * mat, int row_col) { for (int i = 0; i < row_col; i++) for (int j = 0; j < row_col; j++) { cout << *(mat + i * row_col + j) << ", \n"; this->setEdge(i, j, *(mat + i * row_col + j)); } cout << endl; } void Graphm::DFS_ConnectedSubGraph(int n) { this->Mark[n] = VISITED; Visit(n); for (Edge e = this->FristEdge(n); this->IsEdge(e); e = this->NextEdge(e)) if (this->Mark[this->ToVertex(e)] == UNVISITED) DFS_ConnectedSubGraph(this->ToVertex(e)); } void Graphm::BFS_ConnectedSubGraph(int n) { queue<int> Q; Visit(n); Mark[n] = VISITED; Q.push(n); while (! Q.empty()) { int u = Q.front(); Q.pop(); for(Edge e = FristEdge(u); IsEdge(e); e = NextEdge(e)) if (Mark[ToVertex(e)] == UNVISITED) { Visit(ToVertex(e)); Mark[ToVertex(e)] = VISITED; Q.push(ToVertex(e)); } } } #pragma once #include "Graph.h" #include <queue> #ifndef GRAGHM_H #define GRAGHM_H class Graphm : public Graph { public: Graphm(); Graphm(int n) : Graph(n) { int i; matrix = (int **) new int *[numVertex]; for (i = 0; i < numVertex; i++) matrix[i] = new int[numVertex]; for (i = 0; i < numVertex; i++) for (int j = 0; j < numVertex; j++) matrix[i][j] = 0; } ~Graphm(); Edge FristEdge(int oneVertex); Edge NextEdge(Edge preEdge); void setEdge(int from, int to, int weight); void delEdge(int from, int to); void InitWith2DimArray(int * mat, int row_col); void DFS_ConnectedSubGraph(int n); void BFS_ConnectedSubGraph(int n); void Visit(int n) { cout << 'n' << n << " \n"; } //private: int ** matrix; }; #endif // !GRAGHM_H // main.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include "pch.h" #include <iostream> #include "Floyd.h" const int const vertexesNum = 5; int matrix1[vertexesNum][vertexesNum] = { 0 , 8 , INFINITYS, 4 , 3 , INFINITYS, 0 , INFINITYS, INFINITYS, 8 , 6 , 7 , 0 , 10 , 2 , INFINITYS, INFINITYS, INFINITYS, 0 , INFINITYS, 5 , 5 , INFINITYS, INFINITYS, 0 }; int BrokerToPassRomour(Graphm & G, Dist ** D); int main() { std::cout << "Hello World!\n"; Graphm mat[vertexesNum]; mat->InitWith2DimArray((int *)matrix1, vertexesNum); cout << endl; cout << "深度优先周游:\n" << endl; int i; for (i = 0; i < vertexesNum; i++) { mat->clearVisitedMark(); mat->DFS_ConnectedSubGraph(i); cout << endl; } cout << endl; cout << "广度优先周游:\n" << endl; for (i = 0; i < vertexesNum; i++) { mat->clearVisitedMark(); mat->BFS_ConnectedSubGraph(i); cout << endl; } cout << endl; Dist ** floydResult; createFloydResult(floydResult, vertexesNum); int startVertex = BrokerToPassRomour(mat[0], floydResult); cout << "所有顶点间的最短路径:\n" << endl; printAllDistances(floydResult, vertexesNum); cout << endl; for (i = 0; i < vertexesNum; i++) for (int j = 0; j < vertexesNum; j++) if (i != j) printOnePath(floydResult, vertexesNum, i, j); cout << endl; deleteFloydResult(floydResult, vertexesNum); if (startVertex >= 0) cout << "谣言应从 n \n" << startVertex << " 点开始传播!\n" << endl; else cout << "图不连通,问题无解 \n" << endl; return 0; } // 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单 // 调试程序: F5 或调试 >“开始调试”菜单 // 入门提示: // 1. 使用解决方案资源管理器窗口添加/管理文件 // 2. 使用团队资源管理器窗口连接到源代码管理 // 3. 使用输出窗口查看生成输出和其他消息 // 4. 使用错误列表窗口查看错误 // 5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目 // 6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件 int BrokerToPassRomour(Graphm & G, Dist ** D) { int * max; max = new int[G.VerticesNum()]; int min = 0; int pos = 0; int i = 0; for (i = 0; i < G.VerticesNum(); i++) max[i] = -1; Floyd(G, D); for (i = 0; i < G.VerticesNum(); i++) for (int j = 0; j < G.VerticesNum(); j++) if (D[i][j].length > max[i]) max[i] = D[i][j].length; min = max[0]; for (i = 1; i < G.VerticesNum(); i++) if (max[i] < min) { min = max[i]; pos = i; } if (min == INFINITYS) { cout << "此图不连通 \n" << endl; return -1; } return pos; } // pch.cpp: 与预编译标头对应的源文件;编译成功所必需的 #include "pch.h" // 一般情况下,忽略此文件,但如果你使用的是预编译标头,请保留它。 // 入门提示: // 1. 使用解决方案资源管理器窗口添加/管理文件 // 2. 使用团队资源管理器窗口连接到源代码管理 // 3. 使用输出窗口查看生成输出和其他消息 // 4. 使用错误列表窗口查看错误 // 5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目 // 6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件 #ifndef PCH_H #define PCH_H // TODO: 添加要在此处预编译的标头 #endif //PCH_H #include "pch.h" #include "Floyd.h" void createFloydResult(Dist **& D, int vertexesNum) { D = new Dist *[vertexesNum]; for (int i = 0; i < vertexesNum; i++) D[i] = new Dist[vertexesNum]; } void deleteFloydResult(Dist **& D, int vertexesNum) { for (int i = 0; i < vertexesNum; i++) delete[] D[i]; delete[] D; D = NULL; } void printAllDistances(Dist ** D, int vertexesNum) { for (int i = 0; i < vertexesNum; i++) { for (int j = 0; j < vertexesNum; j++) cout << D[i][j].length << " , \n"; cout << endl; } } void printOnePath(Dist ** D, int vertexesNum, int start, int end) { if (D[start][end].length == INFINITYS) return; int * path = new int[vertexesNum]; int vertexCount = 0; int tail = end; while (tail != start) { path[vertexCount++] = D[start][tail].pre; tail = D[start][tail].pre; } cout << "n" << start << "->n" << end << " : "; for (int i = vertexCount - 1; i >= 0; i--) cout << "n" << path[i] << "->"; cout << "n" << end << endl; delete[] path; } void Floyd(Graphm & G, Dist ** D) { int i, j, v; D = new Dist *[G.VerticesNum()]; for (i = 0; i < G.VerticesNum(); i++) D[i] = new Dist[G.VerticesNum()]; for (i = 0; i < G.VerticesNum(); i++) for (j = 0; j < G.VerticesNum(); j++) { if (i == j) { D[i][j].length = 0; D[i][j].pre = i; } else { D[i][j].length = INFINITYS; D[i][j].pre = -1; } } for (i = 0; i < G.VerticesNum(); i++) for (Edge e = G.FristEdge(i); G.IsEdge(e); e = G.NextEdge(e)) { D[i][G.ToVertex(e)].length = G.Weight(e); D[i][G.ToVertex(e)].pre = i; } for (v = 0; v < G.VerticesNum(); v++) for (i = 0; i < G.VerticesNum(); i++) for (j = 0; j < G.VerticesNum(); j++) if (D[i][j].length > (D[i][v].length + D[v][j].length)) { D[i][j].length = D[i][v].length + D[v][j].length; D[i][j].pre = D[v][j].pre; } } #pragma once #include "Graphm.h" #ifndef FLOYD_H #define FLOYD_H class Dist { public: Dist() {} ~Dist() {} int index; int length; int pre; bool operator < (const Dist &arg) { return (length < arg.length); } bool operator == (const Dist &arg) { return (length == arg.length); } bool operator > (const Dist &arg) { return (length > arg.length); } bool operator <= (const Dist &arg) { return (length <= arg.length); } bool operator >= (const Dist &arg) { return (length >= arg.length); } }; void createFloydResult(Dist ** &D, int vertexesNum); void deleteFloydResult(Dist ** &D, int vertexesNum); void printAllDistances(Dist ** D, int vertexesNum); void printOnePath(Dist ** D, int vertexesNum, int start, int end); void Floyd(Graphm &G, Dist ** D); #endif // !FLOYD_H ********************************************************************* "Graphm.cpp": #include "pch.h" #include "Graphm.h" Graphm::Graphm() { } Graphm::~Graphm() { for (int i = 0; i < numVertex; i++) delete[] matrix[i]; delete[] matrix; } Edge Graphm::FristEdge(int oneVertex) { Edge myEdge; myEdge.from = oneVertex; for (int i = 0; i < numVertex; i++) if (matrix[oneVertex][i] != 0 && matrix[oneVertex][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[oneVertex][i]; break; } return myEdge; } Edge Graphm::NextEdge(Edge preEdge) { Edge myEdge; myEdge.from = preEdge.from; if (preEdge.to < numVertex) for (int i = preEdge.to + 1; i < numVertex; i++) if (matrix[preEdge.from][i] != 0 && matrix[preEdge.from][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[preEdge.from][i]; break; } return myEdge; } void Graphm::setEdge(int from, int to, int weight) { if (matrix[from][to] <= 0) { numEdge++; Indegree[to]++; } matrix[from][to] = weight; } void Graphm::delEdge(int from, int to) { if (matrix[from][to] > 0) { numEdge--; Indegree[to]--; } matrix[from][to] = 0; } void Graphm::InitWith2DimArray(int * mat, int row_col) { for (int i = 0; i < row_col; i++) for (int j = 0; j < row_col; j++) { cout << *(mat + i * row_col + j) << ", \n"; this->setEdge(i, j, *(mat + i * row_col + j)); } cout << endl; } void Graphm::DFS_ConnectedSubGraph(int n) { this->Mark[n] = VISITED; Visit(n); for (Edge e = this->FristEdge(n); this->IsEdge(e); e = this->NextEdge(e)) if (this->Mark[this->ToVertex(e)] == UNVISITED) DFS_ConnectedSubGraph(this->ToVertex(e)); } void Graphm::BFS_ConnectedSubGraph(int n) { queue<int> Q; Visit(n); Mark[n] = VISITED; Q.push(n); while (! Q.empty()) { int u = Q.front(); Q.pop(); for(Edge e = FristEdge(u); IsEdge(e); e = NextEdge(e)) if (Mark[ToVertex(e)] == UNVISITED) { Visit(ToVertex(e)); Mark[ToVertex(e)] = VISITED; Q.push(ToVertex(e)); } } } ************************************************************** 第51行 if (matrix[from][to] <= 0) //void Graphm::setEdge(int from, int to, int weight) 引发了未经处理的异常:读取访问权限冲突。 this->matrix 是 0xCDDDCDDE
Risk(Floyd)
Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the armies may move into the newly conquered country. During the course of play, a player often engages in a sequence of conquests with the goal of transferring a large mass of armies from some starting country to a destination country. Typically, one chooses the intervening countries so as to minimize the total number of countries that need to be conquered. Given a description of the gameboard with 20 countries each with between 1 and 19 connections to other countries, your task is to write a function that takes a starting country and a destination country and computes the minimum number of countries that must be conquered to reach the destination. You do not need to output the sequence of countries, just the number of countries to be conquered including the destination. For example, if starting and destination countries are neighbors, then your program should return one. The following connection diagram illustrates the sample input. Input Input to your program will consist of a series of country configuration test sets. Each test set will consist of a board description on lines 1 through 19. The representation avoids listing every national boundary twice by only listing the fact that country I borders country J when I < J. Thus, the Ith line, where I is less than 20, contains an integer X indicating how many "higher-numbered" countries share borders with country I, then X distinct integers J greater than I and not exceeding 20, each describing a boundary between countries I and J. Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow. The next N lines each contain exactly two integers (1 <= A,B <= 20; A!=B) indicating the starting and ending countries for a possible conquest. There can be multiple test sets in the input; your program should continue reading and processing until reaching the end of file. There will be at least one path between any two given countries in every country configuration. Output For each input set, your program should print the following message "Test Set #T" where T is the number of the test set starting with 1. The next NT lines each will contain the result for the corresponding test in the test set - that is, the minimum number of countries to conquer. The test result line should contain the start country code A the string " to " the destination country code B ; the string ": " and a single integer indicating the minimum number of moves required to traverse from country A to country B in the test set. Following all result lines of each input set, your program should print a single blank line. Sample Input 1 3 2 3 4 3 4 5 6 1 6 1 7 2 12 13 1 8 2 9 10 1 11 1 11 2 12 17 1 14 2 14 15 2 15 16 1 16 1 19 2 18 19 1 20 1 20 5 1 20 2 9 19 5 18 19 16 20 Sample Output Test Set #1 1 to 20: 7 2 to 9: 5 19 to 5: 6 18 to 19: 2 16 to 20: 2
e-Market 的计算的问题
Description The city of Hakodate recently established a commodity exchange market. To participate in the market, each dealer transmits through the Internet an order consisting of his or her name, the type of the order (buy or sell), the name of the commodity, and the quoted price. In this market a deal can be made only if the price of a sell order is lower than or equal to the price of a buy price. The price of the deal is the mean of the prices of the buy and sell orders, where the mean price is rounded downward to the nearest integer. To exclude dishonest deals, no deal is made between a pair of sell and buy orders from the same dealer. The system of the market maintains the list of orders for which a deal has not been made and processes a new order in the following manner. For a new sell order, a deal is made with the buy order with the highest price in the list satisfying the conditions. If there is more than one buy order with the same price, the deal is made with the earliest of them. For a new buy order, a deal is made with the sell order with the lowest price in the list satisfying the conditions. If there is more than one sell order with the same price, the deal is made with the earliest of them. The market opens at 7:00 and closes at 22:00 everyday. When the market closes, all the remaining orders are cancelled. To keep complete record of the market, the system of the market saves all the orders it received everyday. The manager of the market asked the system administrator to make a program which reports the activity of the market. The report must contain two kinds of information. For each commodity the report must contain information on the lowest, the average and the highest prices of successful deals. For each dealer, the report must contain information on the amounts the dealer paid and received for commodities. Input The input contains several data sets. Each data set represents the record of the market on one day. The first line of each data set contains an integer n (n < 1000) which is the number of orders in the record. Each line of the record describes an order, consisting of the name of the dealer, the type of the order, the name of the commodity and the quoted price. They are separated by a single space character. The name of a dealer consists of capital alphabetical letters and is less than 10 characters in length. The type of an order is indicated by a string, "BUY" or "SELL". The name of a commodity is a single capital letter. The quoted price is a positive integer less than 1000. The orders in a record are arranged according to time when they were received and the first line of the record corresponds to the oldest order. The end of the input is indicated by a line containing a zero. Output The output for each data set consists of two parts separated by a line containing two hyphen ('-') characters. The first part is output for commodities. For each commodity, your program should output the name of the commodity and the lowest, the average and the highest prices of the successful deals in on line. The name and the prices in a line should be separated by a space character. The average price is rounded downward to the nearest integer. The output should contain only the commodities for which deals are made and the order of the output must be alphabetic. The second part is output for dealers. For each dealer, your program should output the name of the dealer, the amounts the dealer paid and received for commodities. The name and the numbers in a line should be separated by a space character. The output should contain all the dealers who transmitted orders. The order of dealers in the output must be lexicographic on their names. The lexicographic order is the order in which words in dictionaries are arranged. The output for each data set should be followed by a line containing ten hyphen ('-') characters. Sample Input 3 PERLIS SELL A 300 WILKES BUY A 200 HAMMING SELL A 100 4 BACKUS SELL A 10 FLOYD BUY A 20 IVERSON SELL B 30 BACKUS BUY B 40 7 WILKINSON SELL A 500 MCCARTHY BUY C 300 WILKINSON SELL C 200 DIJKSTRA SELL B 100 BACHMAN BUY A 400 DIJKSTRA BUY A 600 WILKINSON SELL A 300 2 ABCD SELL X 10 ABC BUY X 15 2 A SELL M 100 A BUY M 100 0 Sample Output A 150 150 150 -- HAMMING 0 150 PERLIS 0 0 WILKES 150 0 ---------- A 15 15 15 B 35 35 35 -- BACKUS 35 15 FLOYD 15 0 IVERSON 0 35 ---------- A 350 450 550 C 250 250 250 -- BACHMAN 350 0 DIJKSTRA 550 0 MACCARTHY 250 0 WILKINSON 0 1150 ---------- X 12 12 12 -- ABC 12 0 ABCD 0 12 ---------- -- A 0 0 ----------
程序在main处就出现段错误是怎么回事啊?求教
![图片说明](https://img-ask.csdn.net/upload/201512/14/1450105965_975066.png) #include<stdio.h> #include<string.h> #include<malloc.h> #include<stdlib.h> typedef char InfoPtr; typedef char VertexType[4]; typedef int VRType; #define INFINITY 100000 #define MAXSIZE 100 typedef int PathMatrix[MAXSIZE][MAXSIZE][MAXSIZE]; typedef int ShortPathLength[MAXSIZE][MAXSIZE]; typedef enum{DG, DN, UG, UN }GraphKind; typedef struct { VRType adj; InfoPtr *info; }ArcNode, AdjMatrix[MAXSIZE][MAXSIZE]; typedef struct { VertexType vex[MAXSIZE]; AdjMatrix arc; int vexnum, arcnum; GraphKind kind; }MGraph; typedef struct { int row; int col; int weight; } GNode; void CreateGraph(MGraph *N, GNode *value, int vnum, int arcnum, VertexType *ch); void DisplayGraph(MGraph N); void Floyd(MGraph N, PathMatrix path, ShortPathLength dist); void main() { int w, u, v, vnum = 3, arcnum = 4; MGraph N; GNode value[] = {{0,1,5}, {1,0,10}, {1,2,6}, {2,0,9}}; VertexType ch[] = {"v0", "v1", "v2"}; PathMatrix path; ShortPathLength dist; CreateGraph(&N, value, vnum, arcnum, ch); for(v = 0; v < N.vexnum; v++) N.arc[v][v].adj = 0; DisplayGraph(N); Floyd(N, path, dist); printf("顶点之间的最短路径长度矩阵dist:\n"); for(u = 0; u < N.vexnum; u++) { for(v = 0; v < N.vexnum; v++) printf("%6d", dist[u][v]); printf("\n"); } for(u = 0; u < N.vexnum; u++) for(v = 0; v < N.vexnum; v++) if(u != v) printf("%s到%s的最短路径为%d\n", N.vex[u], N.vex[v], dist[u][v]); printf("各顶点之间的最短路径所经过的顶点:\n"); for(u = 0; u < N.vexnum; u++) for(v = 0; v < N.vexnum; v++) if(u != v) { printf("由%s到%s经过: ", N.vex[u], N.vex[v]); for(w = 0; w < N.vexnum; w++) if(path[u][v][w] == 1) printf("%s ", N.vex[w]); printf("\n"); } } void CreateGraph(MGraph *N, GNode *value, int vnum, int arcnum, VertexType *ch) { int i, j, k, w, InfoFlag, len; char s[MAXSIZE]; VertexType v1, v2; N->vexnum = vnum; N->arcnum = arcnum; for(i = 0; i < vnum; i++) strcpy(N->vex[i], ch[i]); for(i = 0; i < N->vexnum; i++) for(j = 0; j < N->vexnum; j++) { N->arc[i][j].adj = INFINITY; N->arc[i][j].info = NULL; } for(k = 0; k < arcnum; k++) { i = value[k].row; j = value[k].col; N->arc[i][j].adj = value[k].weight; } N->kind = DN; } void DisplayGraph(MGraph N) { int i, j; printf("有向网具有%d个顶点%d条弧,顶点依次是:", N.vexnum, N.arcnum); for(i = 0; i < N.vexnum; ++i) { printf("%s ", N.vex[i]); } printf("\n有向网N的:\n"); printf("序号i="); for(i = 0; i < N.vexnum; i++) { printf("%11d", i); } printf("\n"); for(i = 0; i < N.vexnum; i++) { printf(" %6-d ", i); for(j = 0; j < N.vexnum; j++) printf("%-11d", N.arc[i][j].adj); printf("\n"); } } void Floyd(MGraph N, PathMatrix path, ShortPathLength dist) { int u, v, w, i; for(v = 0; v < N.vexnum; v++) for(w = 0; w < N.vexnum; w++) { dist[v][w] = N.arc[v][w].adj; for(u = 0; u < N.vexnum; u++) path[v][w][u] = 0; if(dist[v][w] < INFINITY) { path[v][w][v] = 1; path[v][w][w] = 1; } } for(u = 0; u < N.vexnum; u++) for(v = 0; v < N.vexnum; v++) for(w = 0; w < N.vexnum; w++) if(dist[v][u] < INFINITY && dist[u][w] < INFINITY && dist[v][u] + dist[u][w] < dist[v][w]) { dist[v][w] = dist[v][u] + dist[u][w]; for(i = 0; i < N.vexnum; i++) path[v][w][i] = path[v][u][i] || path[u][w][i]; } }
130 个相见恨晚的超实用网站,一次性分享出来
相见恨晚的超实用网站 持续更新中。。。
字节跳动视频编解码面经
三四月份投了字节跳动的实习(图形图像岗位),然后hr打电话过来问了一下会不会opengl,c++,shador,当时只会一点c++,其他两个都不会,也就直接被拒了。 七月初内推了字节跳动的提前批,因为内推没有具体的岗位,hr又打电话问要不要考虑一下图形图像岗,我说实习投过这个岗位不合适,不会opengl和shador,然后hr就说秋招更看重基础。我当时想着能进去就不错了,管他哪个岗呢,就同意了面试...
win10系统安装教程(U盘PE+UEFI安装)
一、准备工作 u盘,电脑一台,win10原版镜像(msdn官网) 二、下载wepe工具箱 极力推荐微pe(微pe官方下载) 下载64位的win10 pe,使用工具箱制作启动U盘打开软件, 选择安装到U盘(按照操作无需更改) 三、重启进入pe系统 1、关机后,将U盘插入电脑 2、按下电源后,按住F12进入启动项选择(技嘉主板是F12) 选择需要启...
程序员必须掌握的核心算法有哪些?
由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过...
Python——画一棵漂亮的樱花树(不同种樱花+玫瑰+圣诞树喔)
最近翻到一篇知乎,上面有不少用Python(大多是turtle库)绘制的树图,感觉很漂亮,我整理了一下,挑了一些我觉得不错的代码分享给大家(这些我都测试过,确实可以生成) one 樱花树 动态生成樱花 效果图(这个是动态的): 实现代码 import turtle as T import random import time # 画樱花的躯干(60,t) def Tree(branch, ...
大学四年自学走来,这些私藏的实用工具/学习网站我贡献出来了
大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意:文中提到的所有资源,文末我都给你整理好了,你们只管拿去,如果觉得不错,转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...
《奇巧淫技》系列-python!!每天早上八点自动发送天气预报邮件到QQ邮箱
将代码部署服务器,每日早上定时获取到天气数据,并发送到邮箱。 也可以说是一个小人工智障。 思路可以运用在不同地方,主要介绍的是思路。
致 Python 初学者
欢迎来到“Python进阶”专栏!来到这里的每一位同学,应该大致上学习了很多 Python 的基础知识,正在努力成长的过程中。在此期间,一定遇到了很多的困惑,对未来的学习方向感到迷茫。我非常理解你们所面临的处境。我从2007年开始接触 python 这门编程语言,从2009年开始单一使用 python 应对所有的开发工作,直至今天。回顾自己的学习过程,也曾经遇到过无数的困难,也曾经迷茫过、困惑过。开办这个专栏,正是为了帮助像我当年一样困惑的 Python 初学者走出困境、快速成长。希望我的经验能真正帮到你
Java描述设计模式(19):模板方法模式
本文源码:GitHub·点这里 || GitEE·点这里 一、生活场景 通常一款互联网应用的开发流程如下:业务需求,规划产品,程序开发,测试交付。现在基于模板方法模式进行该过程描述。 public class C01_InScene { public static void main(String[] args) { DevelopApp developApp = n...
加快推动区块链技术和产业创新发展,2019可信区块链峰会在京召开
11月8日,由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办,科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。   区块链技术被认为是继蒸汽机、电力、互联网之后,下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力,电力解决了人类基本的生活需求,互联网彻底改变了信息传递的方式,区块链作为构造信任的技术有重要的价值。   1...
C语言魔塔游戏
很早就很想写这个,今天终于写完了。 游戏截图: 编译环境: VS2017 游戏需要一些图片,如果有想要的或者对游戏有什么看法的可以加我的QQ 2985486630 讨论 下面我来介绍一下游戏的主要功能和实现方式 首先是玩家的定义,使用结构体,这个名字是可以自己改变的 struct gamerole { char name[20] = "黑蛋"; //玩家名字 int...
第三个java程序(表白小卡片)
前言: &nbsp;向女神表白啦,作为一个程序员,当然也有爱情啦。只不过,虽然前面两个程序都只是学习了基础的语法结构和向量哈希表。这里涉及的是Swing,awt图形用户界面和一点文件输入输出流的知识。 &nbsp; 表白代码如下: 另附:里面的音乐和图片可以放在一个自己创建的包里面,也可以放在src里面,或者使用绝对路径。至于布局,我自己的使用的是简单的排班,简单的继承。后面的程序会慢慢实现。 ...
8年经验面试官详解 Java 面试秘诀
作者 |胡书敏 责编 | 刘静 出品 | CSDN(ID:CSDNnews) 本人目前在一家知名外企担任架构师,而且最近八年来,在多家外企和互联网公司担任Java技术面试官,前后累计面试了有两三百位候选人。在本文里,就将结合本人的面试经验,针对Java初学者、Java初级开发和Java开发,给出若干准备简历和准备面试的建议。 Java程序员准备和投递简历的实...
知乎高赞:中国有什么拿得出手的开源软件产品?(整理自本人原创回答)
知乎高赞:中国有什么拿得出手的开源软件产品? 在知乎上,有个问题问“中国有什么拿得出手的开源软件产品(在 GitHub 等社区受欢迎度较好的)?” 事实上,还不少呢~ 本人于2019.7.6进行了较为全面的回答,对这些受欢迎的 Github 开源项目分类整理如下: 分布式计算、云平台相关工具类 1.SkyWalking,作者吴晟、刘浩杨 等等 仓库地址: apache/skywalking 更...
化繁为简 - 腾讯计费高一致TDXA的实践之路
导语:腾讯计费是孵化于支撑腾讯内部业务千亿级营收的互联网计费平台,在如此庞大的业务体量下,腾讯计费要支撑业务的快速增长,同时还要保证每笔交易不错账。采用最终一致性或离线补...
Linux网络服务-----实验---PXE和Kickstart的无人值守装机
目录 一.PXE的原理 二.kickstart的原理 三.PXE与kickstart的结合使用自动装机 一.PXE的原理 PXE(preboot execute environment,预启动执行环境)是由Intel公司开发的最新技术,工作于Client/Server的网络模式,支持工作站通过网络从远端服务器下载映像,并由支持通过网络启动操作系统,再启动过程中,终端要求服务器分配IP地址...
究竟你适不适合买Mac?
我清晰的记得,刚买的macbook pro回到家,开机后第一件事情,就是上了淘宝网,花了500元钱,找了一个上门维修电脑的师傅,上门给我装了一个windows系统。。。。。。 表砍我。。。 当时买mac的初衷,只是想要个固态硬盘的笔记本,用来运行一些复杂的扑克软件。而看了当时所有的SSD笔记本后,最终决定,还是买个好(xiong)看(da)的。 已经有好几个朋友问我mba怎么样了,所以今天尽量客观...
A*搜索算法概述
编者按:本文作者奇舞团前端开发工程师魏川凯。A*搜索算法(A-star search algorithm)是一种常见且应用广泛的图搜索和寻径算法。A*搜索算法是通过使用启...
程序员写了一个新手都写不出的低级bug,被骂惨了。
这种新手都不会范的错,居然被一个工作好几年的小伙子写出来,差点被当场开除了。
Java工作4年来应聘要16K最后没要,细节如下。。。
前奏: 今天2B哥和大家分享一位前几天面试的一位应聘者,工作4年26岁,统招本科。 以下就是他的简历和面试情况。 基本情况: 专业技能: 1、&nbsp;熟悉Sping了解SpringMVC、SpringBoot、Mybatis等框架、了解SpringCloud微服务 2、&nbsp;熟悉常用项目管理工具:SVN、GIT、MAVEN、Jenkins 3、&nbsp;熟悉Nginx、tomca...
2020年,冯唐49岁:我给20、30岁IT职场年轻人的建议
点击“技术领导力”关注∆每天早上8:30推送 作者|Mr.K 编辑| Emma 来源|技术领导力(ID:jishulingdaoli) 前天的推文《冯唐:职场人35岁以后,方法论比经验重要》,收到了不少读者的反馈,觉得挺受启发。其实,冯唐写了不少关于职场方面的文章,都挺不错的。可惜大家只记住了“春风十里不如你”、“如何避免成为油腻腻的中年人”等不那么正经的文章。 本文整理了冯...
从顶级黑客到上市公司老板
一看标题,很多老读者就知道我在写什么了。今天Ucloud成功上市,季昕华成为我所熟悉的朋友里又双叒叕一个成功上市的案例。我们认识大概是十五年多吧,如果没记错,第一次见面应该是2004年,...
蓝桥杯知识点汇总:基础知识和常用算法
文章目录基础语法部分:算法竞赛常用API:算法部分数据结构部分 此系列包含蓝桥杯绝大部分所考察的知识点,以及真题题解~ 基础语法部分: 备战蓝桥杯java(一):一般输入输出 和 快速输入输(BufferedReader&amp;BufferedWrite) 备战蓝桥杯java(二):java编程规范和常用数据类型 备战蓝桥杯java(三):常用功能符以及循环结构和分支结构 备战蓝桥杯java(四...
作为一个程序员,CPU的这些硬核知识你必须会!
CPU对每个程序员来说,是个既熟悉又陌生的东西? 如果你只知道CPU是中央处理器的话,那可能对你并没有什么用,那么作为程序员的我们,必须要搞懂的就是CPU这家伙是如何运行的,尤其要搞懂它里面的寄存器是怎么一回事,因为这将让你从底层明白程序的运行机制。 随我一起,来好好认识下CPU这货吧 把CPU掰开来看 对于CPU来说,我们首先就要搞明白它是怎么回事,也就是它的内部构造,当然,CPU那么牛的一个东...
破14亿,Python分析我国存在哪些人口危机!
一、背景 二、爬取数据 三、数据分析 1、总人口 2、男女人口比例 3、人口城镇化 4、人口增长率 5、人口老化(抚养比) 6、各省人口 7、世界人口 四、遇到的问题 遇到的问题 1、数据分页,需要获取从1949-2018年数据,观察到有近20年参数:LAST20,由此推测获取近70年的参数可设置为:LAST70 2、2019年数据没有放上去,可以手动添加上去 3、将数据进行 行列转换 4、列名...
强烈推荐10本程序员在家读的书
很遗憾,这个春节注定是刻骨铭心的,新型冠状病毒让每个人的神经都是紧绷的。那些处在武汉的白衣天使们,尤其值得我们的尊敬。而我们这些窝在家里的程序员,能不外出就不外出,就是对社会做出的最大的贡献。 有些读者私下问我,窝了几天,有点颓丧,能否推荐几本书在家里看看。我花了一天的时间,挑选了 10 本我最喜欢的书,你可以挑选感兴趣的来读一读。读书不仅可以平复恐惧的压力,还可以对未来充满希望,毕竟苦难终将会...
Linux自学篇——linux命令英文全称及解释
man: Manual 意思是手册,可以用这个命令查询其他命令的用法。 pwd:Print working directory 意思是密码。 su:Swith user 切换用户,切换到root用户 cd:Change directory 切换目录 ls:List files 列出目录下的文件 ps:Process Status 进程状态 mkdir:Make directory ...
Python实战:抓肺炎疫情实时数据,画2019-nCoV疫情地图
今天,群里白垩老师问如何用python画武汉肺炎疫情地图。白垩老师是研究海洋生态与地球生物的学者,国家重点实验室成员,于不惑之年学习python,实为我等学习楷模。先前我并没有关注武汉肺炎的具体数据,也没有画过类似的数据分布图。于是就拿了两个小时,专门研究了一下,遂成此文。
疫情数据接口api
返回json示例 { "errcode":0,//0标识接口正常 "data":{ "date":"2020-01-30 07:47:23",//实时更新时间 "diagnosed":7736,//确诊人数 "suspect":12167,//疑是病例人数 "death":170,//死亡人数 "cur...
智力题(程序员面试经典)
NO.1  有20瓶药丸,其中19瓶装有1克/粒的药丸,余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平,怎么找出比较重的那瓶药丸?天平只能用一次。 解法 有时候,严格的限制条件有可能反倒是解题的线索。在这个问题中,限制条件是天平只能用一次。 因为天平只能用一次,我们也得以知道一个有趣的事实:一次必须同时称很多药丸,其实更准确地说,是必须从19瓶拿出药丸进行称重。否则,如果跳过两瓶或更多瓶药...
疫情防控,开发者集结出战!
作者 | 屠敏出品 | CSDN(ID:CSDNnews)2020 年伊始,病毒肆虐,人心惶惶。截止北京时间 1 月 31 日 15 时 30 分,全国确诊新型冠状病毒肺炎的数字已达到了...
相关热词 c# 识别回车 c#生成条形码ean13 c#子控制器调用父控制器 c# 写大文件 c# 浏览pdf c#获取桌面图标的句柄 c# list反射 c# 句柄 进程 c# 倒计时 线程 c# 窗体背景色
立即提问