1419：SPFA(II)

时间限制: 1000 ms         内存限制: 65536 KB

提交数: 1156     通过数: 209

【题目描述】

给定一个有向连通图，求从1到n的最短路。

【输入】

第一行两个整数n,m,代表点数和边数；

接下来m行，每行三个整数s,t,d,代表从s到t有一条长度为d的有向边。

【输出】

输出一个整数表示最短距离。

【输入样例】

2 3

1 2 1

1 2 -1

2 2 0

【输出样例】

-1

【提示】

【数据规模及约定】

N≤20000,M≤40000,1≤S,T≤N,−109≤D≤109

保证没有负环、1可以到达N。

风萧萧兮易水寒，欠了债兮你要还。

我来还债了……

今天讲1419。

欢迎来到模板题目出不去系列。

系列1：

spfa(就是spfa，不是别的）。

算法详见明天或后天的spfa算法（注意看，助我阅读量哦）。

代码：

#include <bits/stdc++.h>

using namespace std;

int n,m,x,y;

long long z;

struct wow

{

  long long dis;

  int num;

};

bool vis[20050];

long long di[20050];

vector<wow> a[20050];

int main()

{

  cin>>n>>m;

  for(int i=1; i<=m; i++)

  {

    scanf("%d%d%lld",&x,&y,&z);

    if(x==y) continue;//排除自环

    wow c;

    c.dis=z;

    c.num=y;

    a[x].push_back(c);

  }//输入

  queue<int> q;

  memset(di,0x3f,sizeof(di));

  di[1]=0;

  vis[1]=1;

  q.push(1);//准备

  while(!q.empty())

  {

    int b=q.front();

    q.pop();

    vis[b]=0;//取出、还原

    for(int i=0; i<a[b].size(); i++)

    {

      wow c=a[b][i];

      if(di[a[b][i].num]>a[b][i].dis+di[b])

      {

        di[a[b][i].num]=a[b][i].dis+di[b];//改值

        if(!vis[a[b][i].num])

        {

          vis[a[b][i].num]=1;

          q.push(a[b][i].num);

        }//推入队

      } //更新

    }

  }

  cout<<di[n]<<endl;

  return 0;

}

好的，模板题，没有太多的总结，搞好算法即可，再见。

附录：我的模板题出不去系列网址：

https://www.jianshu.com/c/6823e7b9b8e5

模板题出不去系列强势来袭！！！