第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路

#include<stdio.h>
int dis[20005],u[200005],v[200005],w[200005];
int main()
{
	int m,n,i,k,check;
	int inf=99999999;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
	for(i=1;i<=n;i++)
		dis[i]=inf;
	dis[1]=0;
	for(k=1;k<=n-1;k++){
		check=0;
		for(i=1;i<=m;i++){
			if(dis[v[i]]>dis[u[i]]+w[i]){
				dis[v[i]]=dis[u[i]]+w[i];
				check=1;}
			}
		if(check==0)
			break;}
	for(i=2;i<=n;i++)
		printf("%d\n",dis[i]);
	return 0;
}

 #include<stdio.h>  
 #include<string.h>  
 #define inf 100000  
 struct In{  
     int e;  
     int w;  
     int next;  
 }map[200010];  
 int dis[20010],Q[20010];  
 int vis[20010],head[20010];  
 void SPFA(int n){  
     int i,j,front,rear,temp;  
     for(i=1;i<=n;i++){  
         dis[i]=inf;  
     }  
     dis[1]=0;vis[1]=1;  
     front=0;rear=1;  
     Q[front]=1;  
     while(front<rear){  
         temp=Q[front++];  
         vis[temp]=0;  
         j=head[temp];  
         while(j>0){  
             if(dis[map[j].e]>map[j].w+dis[temp]){  
                 dis[map[j].e]=map[j].w+dis[temp];  
                 if(!vis[map[j].e]){  
                     Q[rear++]=map[j].e;  
                     vis[map[j].e]=1;   
                 }  
             }  
             j=map[j].next;  
         }  
     }  
 }  
 int main(){  
     int n,m,i,j,a,b,val;  
     while(~scanf("%d%d",&n,&m)){  
         memset(Q,0,sizeof(Q));  
         memset(head,0,sizeof(head));  
         memset(vis,0,sizeof(vis));  
         for(i=1;i<=m;i++){  
             scanf("%d%d%d",&a,&b,&val);  
             map[i].e=b;  
             map[i].w=val;  
             map[i].next=head[a];  
             head[a]=i;  
         }  
         SPFA(n);  
         for(i=2;i<=n;i++){  
             printf("%d\n",dis[i]);  
         }  
     }  
     return 0;  
 } 

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int leng[];

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		List<node> list[] = new ArrayList[n];// 存储路径
		for (int i = 0; i < n; i++)// 声明
		{
			list[i] = new ArrayList<node>();
		}
		leng = new int[n];
		boolean jud[] = new boolean[n];// 判断是否在队列内
		for (int i = 1; i < n; i++) {
			leng[i] = Integer.MAX_VALUE;
		} // 初始最长均为max
		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int l = sc.nextInt();
			list[u - 1].add(new node(v - 1, l));
		}
		Queue<Integer> q1 = new ArrayDeque<Integer>();
		q1.add(0);// 第一个
		while (!q1.isEmpty()) {
			int x = q1.poll();
			jud[x] = false;
			for (int i = 0; i < list[x].size(); i++)// 遍历
			{
				int index = list[x].get(i).x;// x邻居该节点的编号
				int length = list[x].get(i).leng;// x到这个邻居的距离
				if (leng[index] > leng[x] + length) {
					leng[index] = leng[x] + length;
					if (!jud[index])// 队列中没有该点
					{
						q1.add(index);
						jud[index] = true;
					}
				}
			}
		}
		for (int i = 1; i < n; i++) {
			System.out.println(leng[i]);
		}
	}

	static class node {
		int x;
		int leng;

		public node(int x, int leng) {
			this.x = x;
			this.leng = leng;
		}
	}
}

n,m=map(int,input().split())
g=[dict() for i in range(n+1)]
for i in range(m):
    u,v,l=map(int,input().split())
    g[u][v]=l
queue=[1]
visited=[True if i==1 else False for i in range(n+2)]
inf=1000000000
dist=[0 if i==1 else inf for i in range(n+2)]
while queue!=[]:
    rhs=queue.pop(0)
    visited[rhs]=False
    dicts=g[rhs]
    if dicts!={}:
        for key,value in dicts.items():
            if dist[key]>dist[rhs]+value:
                dist[key]=dist[rhs]+value
                if not visited[key]:
                    visited[key]=True
                    queue.append(key)

for i in range(2,n+1):
    print(dist[i])