単一ソースの最短経路(Dijkstraアルゴリズム)
5435 ワード
タイトル:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=208
あなたにn個の点をあげます。m本の無向辺には長さdと費用cがあります。起点sと終点tをあげます。出力起点から終点までの最短距離と費用を要求します。もし最短距離があれば。
複数の路線であれば、出力が一番少ないです。
解析:本題は二重権の最短経路の問題です。もちろん一番の方法は普通の最短やり方と同じです。
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N = 1005;
const int INF = 1<<30;
int map[N][N];
int dist[N];
bool vis[N];
int n,m;
void Init()
{
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
map[i][j] = INF;
}
void Dijkstra(int cur)
{
vis[cur] = 1;
for(int i=1; i<=n; i++)
dist[i] = map[cur][i];
dist[cur] = 0;
for(int i=2; i<=n; i++)
{
int k = cur;
int minval = INF;
for(int j=1; j<=n; j++)
{
if(!vis[j] && dist[j] < minval)
{
minval = dist[j];
k = j;
}
}
vis[k] = 1;
for(int j=1; j<=n; j++)
{
if(!vis[j])
dist[j] = min(dist[j],dist[k] + map[k][j]);
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
Init();
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u++; v++;
map[u][v] = w;
}
int s,t;
scanf("%d%d",&s,&t);
s++; t++;
Dijkstra(s);
if(dist[t] == INF) puts("-1");
else printf("%d
",dist[t]);
}
return 0;
}
Dijkstraはset最適化後、時間複雑度はO(n*log(n)になります。#include <iostream>
#include <string.h>
#include <stdio.h>
#include <set>
using namespace std;
const int N = 1005;
const int INF = 1 << 30;
struct Edge
{
int to;
int w;
int next;
};
Edge edge[N*N];
int head[N],dist[N];
bool vis[N];
int cnt;
struct cmp
{
bool operator()(const int &a,const int &b) const
{
return dist[a] < dist[b] || (dist[a] == dist[b] && a < b);
}
};
set<int,cmp> s;
void add(int u,int v,int w)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].w = w;
head[u] = cnt++;
}
void Init()
{
cnt = 0;
s.clear();
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
for(int i=0;i<N;i++)
dist[i] = INF;
}
void Dijkstra(int v)
{
dist[v] = 0;
s.insert(v);
while(!s.empty())
{
v = *s.begin();
s.erase(v);
vis[v] = 1;
for(int i=head[v];~i;i=edge[i].next)
{
int t = edge[i].to;
if(!vis[t] && dist[t] > dist[v] + edge[i].w)
{
s.erase(t);
dist[t] = dist[v] + edge[i].w;
s.insert(t);
}
}
}
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
Init();
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
int s,t;
scanf("%d%d",&s,&t);
Dijkstra(s);
if(dist[t] == INF) puts("-1");
else printf("%d
",dist[t]);
}
return 0;
}
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=3790 あなたにn個の点をあげます。m本の無向辺には長さdと費用cがあります。起点sと終点tをあげます。出力起点から終点までの最短距離と費用を要求します。もし最短距離があれば。
複数の路線であれば、出力が一番少ないです。
解析:本題は二重権の最短経路の問題です。もちろん一番の方法は普通の最短やり方と同じです。
#include <iostream>
#include <string.h>
#include <stdio.h>
const int N = 1005;
const int INF = 1<<29;
bool vis[N];
int d[N],c[N];
int map[N][N];
int cost[N][N];
int m,n,s,t;
void Init()
{
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
map[i][j] = (i == j) ? 0 : INF;
cost[i][j] = (i == j) ? 0 : INF;
}
}
}
void Dijkstra(int cur)
{
vis[cur] = 1;
for(int i=1; i<=n; i++)
{
d[i] = map[cur][i];
c[i] = cost[cur][i];
}
for(int i=2; i<=n; i++)
{
int k = cur;
int minval = INF;
for(int j=1; j<=n; j++)
{
if(!vis[j] && d[j] < minval)
{
minval = d[j];
k = j;
}
}
vis[k] = 1;
for(int j=1; j<=n; j++)
{
if(!vis[j])
{
if(d[j] > d[k] + map[k][j])
{
d[j] = d[k] + map[k][j];
c[j] = c[k] + cost[k][j];
}
else if(d[j] == d[k] + map[k][j] && c[j] > c[k] + cost[k][j])
c[j] = c[k] + cost[k][j];
}
}
}
if(d[t] == INF) puts("1");
else printf("%d %d
",d[t],c[t]);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
Init();
while(m--)
{
int u,v,x,y;
scanf("%d%d%d%d",&u,&v,&x,&y);
if((map[u][v] > x) || (map[u][v] == x && cost[u][v] > y))
{
map[u][v] = map[v][u] = x;
cost[u][v] = cost[v][u] = y;
}
}
scanf("%d%d",&s,&t);
Dijkstra(s);
}
return 0;
}