蓝桥杯- 算法训练 最短路

 

    

SPFA算法——最短路径

     http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html

  算法训练 最短路  

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

      

问题描述

给定一个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，保证从任意顶点都能到达其他所有顶点。

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define inf 90000
struct node
{
    int now;
    int next;
    int val;
}map[200100];
int n,m,len,head[200100];
int d[200100],vis[200100];
void add(int x,int y,int v)
{
    map[len].now=y;
    map[len].val=v;
    map[len].next=head[x];
    head[x]=len++;
}
void dfs(int u)
{
    vis[u]=1;
    for(int k=head[u];k!=-1;k=map[k].next)
    {
        int v=map[k].now,w=map[k].val;
        if(d[u]+w<d[v])
        {
            d[v]=d[u]+w;
            if(!vis[v])
            {
                dfs(v);
            }
        }
    }
    vis[u]=0;
}
int main()
{
     int a,b,l,i;

   while(~scanf("%d%d",&n,&m))
   {
          len=0;
     memset(head,-1,sizeof(head));
     memset(vis,0,sizeof(vis));
      for(i=2;i<=n;i++)
          d[i]=inf;
        d[1]=0;
     for(i=0;i<m;i++)
     {
         scanf("%d%d%d",&a,&b,&l);
         add(a,b,l);
     }
      dfs(1);
     for(i=2;i<=n;i++)
     {
          printf("%d\n",d[i]);
      }
   }
    return 0;
}
View Cod