安一825 2021-06-18 16:41 采纳率: 0%
浏览 101

信息学奥赛一本通在线测评系统:1382:最短路(Spfa) 代码为什么会运行超时?

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 0x3f3f3f3f; 
int n,m; 
int source,end;
struct edge{
	int to,wight;
	int pre;
}e[3200000]; 

int vertex[320000];
int d[250000];
bool flag[250000];

int cnt = 0;
void add(int v,int u,int w){
	e[++cnt].to = u;
	e[cnt].wight = w;
	e[cnt].pre = vertex[v];
	vertex[v] = cnt;
}

void printGraph(int n){
	for(int i=1;i<=n;i++){
		int index = vertex[i];
		cout<<i<<':';
		while( index ){
			edge newEdge = e[index];
			cout<<newEdge.to<<' ';
			index = newEdge.pre;
		}
		cout<<endl;
	}
}



void spfa(int n){
	queue<int> que;
	que.push(source);
	flag[source] = 1;
	while(!que.empty()){
		int v = que.front();
		flag[v] = 0;
		que.pop();			
		for(int i=vertex[v];i;i=e[i].pre){
			int to = e[i].to;
			int w = e[i].wight;
			if( d[v] + w < d[to] ){
				d[to]  = d[v] + w ;
				if( !flag[to]){
					que.push(to);
					flag[to] = 1;			
				}
			}			
		}
	}
}

int main(){
	cin>>n>>m;
	int v,u,w;
	for(int i=0;i<m;i++){
		cin>>v>>u>>w;
		add(v,u,w);
		add(u,v,w);
	}
	source=1;end=n;
	fill(d,d+100005,MAXN);
	d[source] = 0;
	spfa(n);
	cout<<d[n]<<endl;
	return 0;
}
  • 写回答

3条回答 默认 最新

  • CSDN专家-link 2021-06-18 16:45
    关注

    是超时完成,还是超时都没有完成,像死机或死循环一样呢?

    评论

报告相同问题?

悬赏问题

  • ¥15 读取parquet文件某一列的数据但是输出是整个列名和格式
  • ¥15 机动目标 制导律建模问题
  • ¥100 求Java socks 转发实现Demo
  • ¥20 随身WiFi移动网络访问不了
  • ¥50 RAD_XE11.3获取android11手机的IMEI码
  • ¥15 linux的gcc命令报错
  • ¥20 如何再GIS用海岸线建立缓冲区
  • ¥15 codeblock遇到问题了,求帮助😭
  • ¥15 Qt6.8.0加载网页MSVC2022
  • ¥15 360浏览器m2的这个值