最短路默写1最短路默写2

问题描述

有一无负权有向图。求指定两点间的最短路径。

输入格式

输入：第一行，两个数字n和m，表示n个顶点，m条边
接下来的m行，每行三个整数，分别表示边的起点、终点和边的长度
最后一行 两个整数 x y 表示求从点x到点y的最短路径

输出格式

输出：一行，一个整数，最短路径长度

样例输入 1

3  3
1  2  5
1  3  2
3  2  1
1  2

样例输出 1

3

样例输入 2

4 5
1 2 10
1 3 1
3 2 6
3 4 2
4 2 3
1 2

样例输出 2

6

提示

注：所有数据都不超过100

#include
using namespace std;
queueq;
int dis[105],cnt[105],n,m,Map[105][105],ax,ay;
bool f[105],ha;
void sp(int start){
	int i,x;
	ha=false;
	for(i=1;i<=n;i++){	dis[i]=100000000;cnt[i]=0;}
	q.push(start);
	f[start]=true;
	dis[start]=0;
	cnt[start]=1;
	while(!q.empty()){
		x=q.front();
		q.pop();
		f[x]=false;
		for(i=1;i<=n;i++){
			if(dis[x]+Map[x][i] 
最短路默写2
 
    
时间限制 : 10000 MS   空间限制 : 524288 KB
问题描述
 
有一无负权有向图。求指定两点间的最短路径。
 
输入格式
 
第一行，两个数字n和m，表示n个顶点，m条边
 接下来的m行，每行三个整数，分别表示边的起点、终点和边的长度
 最后一行 两个整数 x y 表示求从点x到点y的最短路径
 
输出格式
 
一行，一个整数，最短路径长度
 
样例输入
 
3 3
 1 2 5
 1 3 2
 3 2 1
 1 2
 
样例输出
 
3
 
提示
 
n<=400000
 m<=2000000
 节点编号从1到n
 每条边的长度都是0到10^9的整数

 5组小数据，3组大数据
 
#include
using namespace std;
const long long INF=99999999999999999ll;
const int MAX_N=400005;
const int MAX_M=4000005;
int N,M,A,B;
struct Edge{
	int x,y,z,next;
}e[MAX_M];
int elast[MAX_N];
struct PQNode{
	int u;
	long long dis;
	PQNode(int u_,long long dis_){
		u=u_;
		dis=dis_;
	}
};
bool operator<(PQNode a,PQNode b){
	return a.dis>b.dis;
}
long long dis[MAX_N];
bool mark[MAX_N];
int main(){
	scanf("%d%d",&N,&M);
	for(int i=1,j=1;i<=M;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[j].x=x;
		e[j].y=y;
		e[j].z=z;
		e[j].next=elast[x];
		elast[x]=j++;
		e[j].x=x;
		e[j].y=y;
		e[j].z=z;
		e[j].next=elast[y];
		elast[y]=j++;
	}
	scanf("%d%d",&A,&B);
	for(int i=1;i<=N;i++){
		dis[i]=INF;
		mark[i]=false;
	}
	dis[A]=0;
	priority_queue pq;
	pq.push(PQNode(A,0));
	while(!pq.empty()){
		int u=pq.top().u;
		pq.pop();
		if(mark[u])	continue;
		if(u==B)	break;
		mark[u]=true;
		for(int j=elast[u];j;j=e[j].next){
			int v=e[j].y;
			if(dis[v]>dis[u]+e[j].z){
				dis[v]=dis[u]+e[j].z;
				pq.push(PQNode(v,dis[v]));
			}
		}
	}
	printf("%lld",dis[B]);
	return 0;
}