$dijkstra$算法 (邻接矩阵) (最短路径问题)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 2000010, INF = 1000000000;
int n, m;
int g[N][N], dist[N]; // g[][]存储图的邻接矩阵, dist[]表示每个点到起点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
void dijkstra()
{
for (int i = 1; i <= n; i++) dist[i] = INF;
dist[1] = 0;
for (int i = 0; i < n; i++)
{
int id, mind = INF;
for (int j = 1; j <= n; j++)
if (!st[j] && dist[j] < mind)
{
mind = dist[j];
id = j;
}
st[id] = 1;
for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[id] + g[id][j]);
}
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = INF;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
dijkstra();
cout << dist[n] << endl;
return 0;
}
初始化：
for(int i = 0; i < N; i++){
vis[i] = 1, dis[i] =INF;
for(int j = 0; j < N; j++) g[i][j] = INF;
核心代码：
while(t != s){
Min = inf;
for(int i = 0; i <= n; i++){
if(!vis[i]) continue;//我们标记起始点为0
if(Map[t][i] != inf)
dis[i] = min(dis[i], dis[t]+Map[t][i]);
if(dis[i] < Min) Min = dis[i], nxt = i;
}
if(Min == inf) break;
t = nxt, vis[nxt] = 0;
}
题目表述： 一个人的旅行
【问题描述】
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
【输入形式】
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个(起始点)，草儿想去的地方有D个(终点)；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。
【输出形式】
输出草儿能去某个喜欢的城市的最短时间。
【样例输入】
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
【样例输出】
9
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const int INF=0X3f3f3f3f;
int g[N][N], vis[N], dis[N];
int main(){
int T, S, D, a, b,d, time, s, t, next, Min;
while(scanf("%d %d %d", &T, &S, &D) == 3){
for(int i = 0; i < N; i++){
vis[i] = 1, dis[i] =INF;
for(int j = 0; j < N; j++) g[i][j] = INF;
}
for(int i = 0; i < T; i++){
scanf("%d %d %d", &a, &b, &d);
g[a][b] = min(g[a][b], d);
g[b][a] = g[a][b];
}
s = 0, t = 1001;//注意这个起始点的范围
for(int i = 0; i < S; i++) //虚拟起始点
scanf("%d", &a), g[s][a] = g[a][s] = 0;
for(int i = 0; i < D; i++) //虚拟结点
scanf("%d", &b), g[t][b] = g[b][t] = 0;
vis[s] = 0, dis[s] = 0;
while(s != t){
Min = INF;
for(int i = 0; i < 1002; i++){//i的起始点不可以是s，t
if(!vis[i]) continue;
if(g[s][i] != INF)
dis[i] = min(dis[i], dis[s]+g[s][i]);
if(dis[i] < Min) Min = dis[i], next = i;
}
if(Min == INF) break;
s = next, vis[next] = 0;
}
printf("%d\n", dis[t] == INF ? -1 : dis[t]);
}
return 0;
}
题目表述： Choose the best route
【问题描述】
One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.
【输入形式】
There are several test cases.
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.
【输出形式】
The output contains one line for each data set : the least time Kiki needs to spend ,if it’s impossible to find such a route ,just output “-1”.
【样例输入】
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
【样例输出】
1
-1
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 1005
#define inf 0x7fffffff
int Map[MAX_N][MAX_N], vis[MAX_N], dis[MAX_N];
int main(){
int n, m, s, p, q, t, w, nxt, Min;
while(scanf("%d %d %d", &n, &m, &s) == 3){
for(int i = 0; i <= n; i++){
vis[i] = 1, dis[i] = inf;
for(int j = 0; j <= n; j++) Map[i][j] = inf;
}
while(m--){
scanf("%d %d %d", &p, &q, &t);
Map[p][q] = min(Map[p][q], t);
// Map[q][p] = Map[p][q];
}
scanf("%d", &w);
while(w--) scanf("%d", &p), Map[0][p] = Map[p][0] = 0;
t = 0, vis[t] = 0, dis[t] = 0;
while(t != s){
Min = inf;
for(int i = 0; i <= n; i++){
if(!vis[i]) continue;
if(Map[t][i] != inf)
dis[i] = min(dis[i], dis[t]+Map[t][i]);
if(dis[i] < Min) Min = dis[i], nxt = i;
}
if(Min == inf) break;
t = nxt, vis[nxt] = 0;
}
printf("%d\n", dis[s] == inf ? -1 : dis[s]);
}
return 0;
}
题目表述：畅通工程续
【问题描述】某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
【输入形式】
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
【输出形式】
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
【样例输入】
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
【样例输出】
2
-1
#include<bits/stdc++.h>
using namespace std;
const int N=210;
const int INF=0x3f3f3f3f;
int g[N][N], vis[N], dis[N];
int main(){
int n, m, a, b, d, s, t, next, Min;
while(scanf("%d %d", &n, &m) == 2){
for(int i = 0; i < n; i++){
vis[i] = 1, dis[i] = INF;
for(int j = 0; j <n; j++)
g[i][j] = INF;
}
for(int i = 0; i < m; i++){
scanf("%d %d %d", &a, &b, &d);
g[a][b] = min(g[a][b], d);
g[b][a] = g[a][b];
}
scanf("%d %d", &s, &t);
vis[s] = 0, dis[s] = 0;
while(s != t){
Min = INF;
for(int i = 0; i < n; i++){
if(!vis[i]) continue;
if(g[s][i] != INF) dis[i] = min(dis[i], dis[s]+g[s][i]);
if(dis[i] < Min) Min = dis[i], next = i;
}
if(Min == INF) break;
s = next, vis[next] = 0;
}
printf("%d\n", dis[t] == INF ? -1 : dis[t]);
}
return 0;
}
map+dijkstra
该题数据范围很大，我们可以采用两种方式来解决，
第一种就是离散化，不过处理起来稍微麻烦点，
第二种就是我们之前学到的链式前向星+map建图
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,int> PLI;
const int N=2e5+10,M=N*2;
int h[N],e[M],ne[M],w[M],idx;
ll dist[M];
bool st[M];
map<ll,int>mp;
int cnt=1;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
ll dij()
{
priority_queue<PLI,vector<PLI>,greater<PLI>>q;
for(int i=1;i<=cnt;i++)
{
dist[i]=1e18;
}
dist[1]=0;
q.push({0,1});
while(!q.empty())
{
auto t=q.top();
q.pop();
int u=t.y;
if(st[u])continue;
st[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[u]+w[i])
{
dist[j]=dist[u]+w[i];
q.push({dist[j],j});
}
}
}
return dist[2];
}
int main()
{
int m,s;
ll x,y;
memset(h,-1,sizeof h);
scanf("%d%lld%lld%d",&m,&x,&y,&s);
mp[x]=cnt++;
mp[y]=cnt++;
for(int i=1;i<=m;i++)
{
int z,op;
scanf("%lld%lld%d%d",&x,&y,&z,&op);
if(!mp[x]) mp[x]=cnt++;
if(!mp[y]) mp[y]=cnt++;
add(mp[x],mp[y],z);
if(op==2) add(mp[y],mp[x],z);
}
ll ans=dij();
if(ans==1e18) puts("-1");
else printf("%lld\n",(ans+s-1)/s);
}
