嗷 信誓旦旦独立写完 没想到 嗷 Dijsktra算法还是写不出来
我甚至连你的名字都拼错了,噗……
这道题需要D算法和DFS算法结合……
没错DFS我也忘光了 嘿嘿
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define INF 99999999
int road[500][500];
int cost[500][500] = { 0 };
int w[500] = { 0 };
int vis[500] = { 0 };
int dis[500];
int pre[500];
int N, M, start, des;//城市数目,高速数目,起点,终点
void Dijkstra(int st, int num)
{
dis[st] = 0;
for (int i = 0; i < num; i++)
{
int u = -1, MIN = INF;
for (int j = 0; j < num; j++)
{
if (vis[j] == 0 && dis[j] < MIN)
{
u = j;
MIN = dis[j];
}
}
if (u == -1) return;
vis[u] = 1;
for (int v = 0; v < num; v++)
{
if (vis[v] == 0 && road[u][v] != INF)
{
if (dis[u] + road[u][v] < dis[v])
{
dis[v] = dis[u] + road[u][v];
w[v] = w[u] + cost[u][v];
pre[v] = u;
}
else if (dis[u] + road[u][v] == dis[v] && w[u] + cost[u][v] < w[v])
{
w[v] = w[u] + cost[u][v];
pre[v] = u;
}
}
}
}
}
void Dfs(int fina)
{
if (fina == start)
{
return;
}
Dfs(pre[fina]);
cout << pre[fina] << " ";
}
int main()
{
cin >> N >> M >> start >> des;
fill(road[0], road[0] + 500 * 500, INF);
fill(dis, dis + 500, INF);
int s, d;
while (M--)
{
cin >> s >> d;
cin >> road[s][d] >> cost[s][d];
road[d][s] = road[s][d];
cost[d][s] = cost[s][d];
}
Dijkstra(start, N);
Dfs(des);
cout << des<<" "<<dis[des] << " " << w[des];
return 0;
}
然后逐渐意识到……scanf_s和printf_s的好用,太香了……
来个D算法模板……
for(从头到尾)
{
定义两个U变量 u=-1;MIN=INF;
for(从头到尾)
{
if(vis==0&&dis<MIN)
u=...
}
u的判定及定义
u=-1就return 反正 vis[u]=1
for(从头到尾)
{
筛选条件
}
}
哈哈哈哈哈我不信我记不住……