蓝桥杯算法训练最短路（Bellman-Ford算法）

绝地灬酷狼 2024-02-17 20:39 15阅读 0赞

算法训练 最短路

时间限制：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，保证从任意顶点都能到达其他所有顶点。

详细记录

<table> 
 <thead></thead>             
 <tbody> 
  <tr> 
   <th>评测点序号</th> 
   <th>评测结果</th> 
   <th>得分</th> 
   <th>CPU使用</th> 
   <th>内存使用</th> 
   <th>下载评测数据</th> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>0ms</td> 
   <td>1.507MB</td> 
   <td><a href="http://lx.lanqiao.cn/detail.page?submitid=1585896###" rel="nofollow">输入</a> <a href="http://lx.lanqiao.cn/detail.page?submitid=1585896###" rel="nofollow">输出</a></td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>0ms</td> 
   <td>1.507MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>0ms</td> 
   <td>1.507MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>0ms</td> 
   <td>1.535MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>0ms</td> 
   <td>1.535MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>78ms</td> 
   <td>2.398MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>15ms</td> 
   <td>1.734MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>15ms</td> 
   <td>1.921MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>218ms</td> 
   <td>4.613MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td><span>正确</span></td> 
   <td>10.00</td> 
   <td>421ms</td> 
   <td>7.898MB</td> 
   <td><a href="http://lx.lanqiao.cn/help.page#vip" style="color:red" rel="nofollow">VIP特权</a></td> 
  </tr> 
 </tbody> 
</table>

分析：用Bellman-Form算法，算法复杂度（mn），但是很多时候很快就能算出

AC代码：

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    #define INF 500000000
    const int maxn=20000+10;
    struct Edges{
    	int from,to,dist;
    	Edges(int from,int to,int dist):from(from),to(to),dist(dist){}
    };
    
    int d[maxn];
    int inq[maxn];
    vector<Edges>edges;
    vector<int>g[maxn];
    int n,m;
    
    void bellman_ford(){
    	memset(inq,0,sizeof(inq));
    	for(int i=2;i<=n;i++)d[i]=INF;
    	d[1]=0;
    	queue<int>q;
    	q.push(1);
    	inq[1]=1;
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    	
    		inq[u]=0;
    		for(int i=0;i<g[u].size();i++){
    			Edges e=edges[g[u][i]];
    			if(d[e.to]>d[e.from]+e.dist && d[e.from]<INF){
    				d[e.to]=d[e.from]+e.dist;
    				if(!inq[e.to]){
    					q.push(e.to);
    					inq[e.to]=1;
    				}
    			}
    		}
    	}
    }
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=0;i<m;i++){
    			int a,b,c;
    			scanf("%d%d%d",&a,&b,&c);
    			edges.push_back(Edges(a,b,c));
    			int len=edges.size();
    			g[a].push_back(len-1);
    		}
    		
    		bellman_ford();
    		for(int i=2;i<=n;i++){
    			printf("%d\n",d[i]);
    		}
    		edges.clear();
    		for(int i=0;i<n;i++)g[i].clear();
    	}
    	return 0;
    }