Big Truck（Dijkstra）

2023-10-24 21:33

文章标签 dijkstra big truck

本文主要是介绍Big Truck（Dijkstra），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
带权最短路，Dijkstra模板题
一开始傻傻的用Floyd求，怎么也算不对，后来又用DFS，最后一个样例超时…最后用Dijkstra求的…
后来上网查的资料才知道Dijkstra是经典的求取带权最短路算法.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n,t[105],m,a,b,d;
int vis[105];
int g[105][105];
int val[105][105];
int cost[105];void dijkstra(int u)
{int dist[105];for(int i=1; i<=n; i++){dist[i] = g[u][i];if(g[u][i]!=N)cost[i] = t[u]+t[i];}vis[u] = 1;int k,minn;while(true){k=-1,minn = N*5;for(int i=1; i<=n; i++){if(dist[i]<minn&&!vis[i]){k=i;minn = dist[i];}}if(k==-1)break;vis[k] = 1;for(int i=1; i<=n; i++){if(!vis[i]){if(dist[i]>dist[k]+g[k][i]){dist[i] = dist[k]+g[k][i];cost[i] = cost[k]+t[i];}else if(dist[i]==dist[k]+g[k][i]){if(cost[i]<cost[k]+t[i]){cost[i] = cost[k]+t[i];}}}}}if(dist[n]==N)cout<<"impossible"<<endl;elsecout<<dist[n]<<' '<<cost[n]<<endl;
}int main()
{cin>>n;for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)g[i][j] = N;}for(int i=1; i<=n; i++)cin>>t[i];cin>>m;for(int i=1; i<=m; i++){cin>>a>>b>>d;g[a][b] = g[b][a] = d;}dijkstra(1);return 0;
}