文章

1

粉丝

593

获赞

3

访问

9.8k

头像
迪杰斯特拉算法
P1666 中南大学机试题
发布于2020年3月25日 22:29
阅读数 9.8k

#include<iostream>
#include<stack>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
#define MAXX 1010
#define INFF 0x3f3f3f3f
int g[MAXX][MAXX];
bool vis[MAXX];
int dis[MAXX];
int n,m,s,t,a;
void dij(){
	for(int i=1;i<=n;++i){
		dis[i]=g[s][i];
		vis[i]=0;
	}
	dis[s]=0;
	int min,k;
	for(int i=1;i<=n;++i){
		min=INFF;
		for(int j=1;j<=n;++j)
			if(vis[j]==0&&dis[j]<min){
				min=dis[j];
				k=j;
			}
		vis[k]=1;
		for(int j=1;j<=n;++j)
			if(vis[j]==0&&dis[j]>dis[k]+g[k][j])
				dis[j]=dis[k]+g[k][j];
	}
	if(dis[t]>a) cout<<"KENG"<<endl;
	else cout<<"YES "<<dis[t]<<endl;
}
int main(){
	while(cin>>n>>m>>s>>t>>a){
		memset(g,INFF,sizeof(g));
		int x,y,z,wait;
		for(int i=1;i<=m;++i)...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发