codevs 1557【热浪】
|
500
|
dijkstra,spfa,图论,最短路,算法
|
Dewct

614 字
|
3 分钟

题目描述 Description

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。
FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。
给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入描述 Input Description

第一行: 4个由空格隔开的整数: T, C, Ts, Te
第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出描述 Output Description

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

样例输入 Sample Input

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

5->6->1->4 (3 + 1 + 3)

 
最短路，还是裸的(用邻接表存图)…………
首先裸的dijkstra

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_V = 2500 + 5;
const int MAX_E = 6200 + 5;
int V, E, Ts, Te, tot;
int d[MAX_V], first[MAX_V], next[MAX_E << 1];
bool done[MAX_V];
struct edge{
int from, to, cost;
}es[MAX_E << 1];
void init()
{
    memset(first,-1,sizeof(first));
    memset(d,0x3f,sizeof(d));
    tot = 0;
}
void build(int f,int t,int d)
{
    es[++tot] = (edge){    f,t,d};
    next[tot] = first[f];
    first[f] = tot;
}
void dijkstra(int s)
{
    d[s] = 0;
    while(true)
    {
        int v = -1;
        for(int i = 1; i <= V; i ++)
            if(!done[i] && (v == -1 || d[i] < d[v]))
                v = i;
                if(v == -1)    break;
                done[v] = 1;
        for(int i = first[v]; i != -1; i = next[i])
        {
            int u = es[i].to;
            d[u] = min(d[u], d[v] + es[i].cost);
        }
    }
}
int main()
{
    cin >> V >> E >> Ts >> Te;
    init();
    for(int i = 1; i <= E; i ++)
    {
        int ff, tt, dd;
        cin >> ff >> tt >> dd;
        build(ff,tt,dd);
        build(tt,ff,dd);
    }
    dijkstra(Ts);
    cout << d[Te] << endl;
    return 0;
}

 
然后优化后的dijkstra
用的是重载运算符后变成小根堆的优先队列因为我们每次只需要权值最小的边，所以最快的速度便是堆

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxx = 233333;
int t, c, ts, te, tot;
int d[maxx], first[maxx], next[maxx];
bool used[maxx];
struct edge
{
	int from, to, cost;
}es[maxx];
struct qer//存的是当前的边的序号和权值
{
	int num, d;
}qq[maxx];
bool operator < (qer a, qer b)//重载运算符
{
	return a.d > b.d;
}
priority_queue <qer> q; //优先队列
void init()
{
	memset(d, 0x3f, sizeof(d));
	memset(first, -1, sizeof(first));
	tot = 0;
}
void build(int f, int t, int d)
{
	es[++tot] = (edge){f, t, d};
	next[tot] = first[f];
	first[f] = tot;
}
void dijsktra(int s)
{
	q.push((qer){s, 0});
	d[s] = 0;
	used[s] = 1;
	while(!q.empty())
	{
		int now = q.top().num, dist = q.top().d;
		used[now] = 1;
		q.pop();
		for(int i = first[now];i != -1;i = next[i])
		{
			int v = es[i].to;
			if(d[v] > d[now] + es[i].cost)
			{
				d[v] = d[now] + es[i].cost;
				if(!used[v])//如果没被访问，我们就加入堆中进行扩展
					q.push((qer){v, d[v]});
			}
		}
	}
}
int main()
{
	init();
	cin>>t>>c>>ts>>te;
	for(int i = 1;i <= c;i ++)
	{
		int ff, tt, dd;
		scanf("%d%d%d", &ff, &tt, &dd);
		build(ff, tt, dd);
		build(tt, ff, dd);
	}
	dijsktra(ts);
	cout<<d[te]<<endl;
	return 0;
}

 
 
 
接下来神器登场  spfa

/*
作者:Loi_f
题目:p1557 热浪
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int t, c, ts, te, tot;
const int max_x = 2500 + 5;
const int max_v = 6500 + 5;
int d[max_x], first[max_x], next[max_v << 1];
bool used[max_x];
queue <int> q;
struct edge
{
	int from, to, cost;
}es[max_v << 1];
void init()
{
	memset(d, 0x3f, sizeof(d));
	memset(first, -1, sizeof(first));
	tot = 0;
}
void build(int ff, int tt, int dd)
{
	es[++tot] = (edge){ff, tt, dd};
	next[tot] = first[ff];
	first[ff] = tot;
}
void spfa(int s)
{
	d[s] = 0;
	q.push(s);
	used[s] = 1;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		used[u] = 0;
		for(int i = first[u];i != -1;i = next[i])
		{
			int v = es[i].to;
			if(d[v] > d[u] + es[i].cost)
			{
				d[v] = d[u] + es[i].cost;
				if(!used[v])
				{
					q.push(v);
					used[v] = 1;
				}
			}
		}
	}
}
int main()
{
	init();
	cin>>t>>c>>ts>>te;
	for(int i = 1;i <= c;i ++)
	{
		int f, t, d;
		cin>>f>>t>>d;
		build(f, t, d);
		build(t, f, d);
	}
	spfa(ts);
	cout<<d[te]<<endl;
	return 0;
}

 

上一篇
下一篇