算法训练 最短路  

时间限制：1.0s   内存限制：256.0MB

   

锦囊1

 

锦囊2

 

锦囊3

 

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3 1 2 -1 2 3 -1 3 1 2

样例输出

-1 -2

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

 

题解：

由于有环，有负权，故用bellman-ford

由于数据有点大，故用队列进行优化

506328

609738062@qq.com

04-07 17:24

1.055KB

C++

正确

100

171ms

4.003MB

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
            6  7 using namespace std; 8  9 const int N = 20005;10 const int inf = 0x3f3f3f3f;11 12 typedef struct13 {14     int to;15     int dis;16 }PP;17 18 int n,m;19 vector
          
            bian[N];20 int v[N];21 int vis[N];22 23 void bellman()24 {25 queue
           
             que;26 int te,nt;27 que.push(1);28 vis[1]=1;29 int i;30 int dis;31 while(que.size()>=1)32 {33 te=que.front();34 que.pop();35 for(i=0;i
            
             v[te]+dis){39 v[nt]=v[te]+dis;40 if(vis[nt]==0){41 vis[nt]=1;42 que.push(nt);43 }44 }45 }46 vis[te]=0;47 }48 }49 50 int main()51 {52 int i,j;53 int uu,vv,l;54 PP te;55 //freopen("data.in","r",stdin);56 //while(scanf("%d%d",&n,&m)!=EOF)57 scanf("%d%d",&n,&m);58 {59 memset(vis,0,sizeof(vis));60 fill(v,v+n+1,inf);61 v[1]=0;62 for(i=0;i<=n;i++){63 bian[i].clear();64 //printf(" i=%d v=%d\n",i,v[i]);65 }66 for(i=1;i<=m;i++){67 scanf("%d%d%d",&uu,&vv,&l);68 te.to=vv;te.dis=l;69 bian[uu].push_back(te);70 }71 bellman();72 for(i=2;i<=n;i++){73 printf("%d\n",v[i]);74 }75 }76 return 0;77 }