C++结构体加二维数组初始化问题(图的最短路径)
解决时间 2021-02-26 06:49
- 提问者网友:抽煙菂渘情少年
- 2021-02-25 16:47
#include
using namespace std;
#define MaxValue Int_Max
const int NumEdges = 15;
const int NumVertices = 6;
typedef char VertexData;
typedef int EdgeData;
typedef struct
{
VertexData vexList[NumVertices];
EdgeData Edge[NumVertices][NumVertices];
int n;
int e;
} MTGraph;
void main()
{
MTGraph R;
R.n=6;
R.Edge[NumVertices][NumVertices]= {{0 ,2 ,3 ,4 ,5 ,4 },
{2 ,0 ,3 ,1 ,99,2 },
{3 ,3 ,0 ,4 ,5 ,2 },
{4 ,1 ,4 ,0 ,3 ,1 },
{5 ,99,5 ,3 ,0 ,3 },
{4 ,2 ,2 ,1 ,3 ,0 }};
}
这样初始化数组哪里出问题了?
还有,有谁有最短路径的完整程序 C的和C++的都可以
最佳答案
- 五星知识达人网友:胯下狙击手
- 2021-02-25 17:45
都是原创。
最短路SPFA算法:
#define oo 10000000
#include
#include
using namespace std;
ifstream fin("sssp.in");
ofstream fout("sssp.out");
int q[1000000];
int map[10001][10001];
int dist[10001],nin[10001];
bool isin[10001],vis;
int main()
{
int n,m,s,a,b,c,i,j,h=1,t=1,now;
memset(isin,false,sizeof(isin));
memset(nin,0,sizeof(nin));
memset(q,0,sizeof(q));
fin >> n >> m >> s;
for(i=1;i<=n;i++)
{
dist[i]=oo;
for(j=1;j<=n;j++)
map[i][j]=oo;
}
for(i=1;i<=m;i++)
{
fin >> a >> b >> c;
map[a][b]=min(map[a][b],c);
//map[b][a]=min(map[b][a],c);
}
dist[s]=0;
q[1]=s;
isin[s]=true;
nin[s]++;
do
{
now=q[h];
isin[now]=false;
for(i=1;i<=n;i++)
if(dist[now]+map[now][i]
{
dist[i]=dist[now]+map[now][i];
if(!isin[i])
{
q[++t]=i;
isin[i]=true;
nin[i]++;
}
if(nin[i]>n)
{
fout << -1 << endl;
return 0;
}
}
h++;
}while(h<=t);
for(i=1;i<=n;i++)
if(dist[i]==oo)
fout << "NoPath" << endl;
else
fout << dist[i] << endl;
return 0;
}
最短路Dijkstra算法。
//The Shortest Path (Dijkstra)
#include
using namespace std;
int n,graph[1001][1001];
const int MAX=300000000;
void Dijkstra(int vstart)
{
int i,k=n-1,minweight,minv;
bool visited[1001]={false};
visited[vstart]=true;
while(k)
{
minweight=MAX;
for(i=1;i<=n;i++)
if(!visited[i]&&graph[vstart][i]
{
minv=i;
minweight=graph[vstart][i];
}
visited[minv]=true;
for(i=1;i<=n;i++)
if(!visited[i]&&graph[vstart][minv]+graph[minv][i]
k--;
}
}
int main()
{
ifstream fin("Dijkstra.in");
ofstream fout("Dijkstra.out");
int i,j,vstart;
fin>>n>>vstart;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
fin>>graph[i][j];
if(i==j) continue;
if(graph[i][j]==0) graph[i][j]=MAX;
}
Dijkstra(vstart);
fout<
for(i=2;i<=n;i++) fout<<' '<
fout<
return 0;
}
全部回答
- 1楼网友:第幾種人
- 2021-02-25 18:50
[ol][*]#include[i][*]using namespace std;[*][*]struct cell[*]{[*]int num; [*]bool per; [*]};[*]const int size=2;[*]void playgame(cell board[size][size], int numtowers)[*]{[*]for(int i=0;i
我要举报
大家都在看
推荐资讯