鄙人不才，此中鄙陋甚多，望海涵！！！

题目描述

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！

他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。

农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 C 条直接连接 2 个城镇的道路。

每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。

求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。

输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;

第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。

输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。

数据保证至少存在一条道路。

数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000

输入样例

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

输出样例

7

算法1

(朴素dijkstra) $O(n^2)$

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=3000;

int g[N][N],dist[N];
int n,m,s,e;
bool st[N];

int dijkstra(int s,int e)
{
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    for(int i=1;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++) if(!st[j] && (t==-1||dist[t]>dist[j]))  t=j;
        st[t]=true;
        for(int j=1;j<=n;j++)    dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    return dist[e];
}

int main()
{
    cin>>n>>m>>s>>e;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        g[a][b]=g[b][a]=min(g[a][b],w);
    }
    int t=dijkstra(s,e);
    cout<< t <<endl;
    return 0;
}

算法2

(堆优化dijkstra) $O((n+m)logm)$

时间复杂度查了好久，说什么的也有，保险起见，这里就采用那个最高的吧！

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=3000,M=20000;

typedef pair<int,int> PII;

int h[N],w[M],e[M],ne[M],idx;
bool ste[N];
priority_queue<PII,vector<PII>,greater<PII>> heap;

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

int dijkstra(int st,int ed)
{
    int dist[M];
    memset(dist,0x3f,sizeof dist);
    dist[st]=0;
    heap.push({0,st});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        if(ste[t.second]) continue;
        ste[t.second]=true;
        //int distance=t.first,res=t.second;
        for(int i=h[t.second];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>t.first+w[i])
            {
                dist[j]=t.first+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    return dist[ed];
}

int main()
{
    int n,m,st,ed;
    cin>>n>>m>>st>>ed;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w),add(b,a,w);
    }
    int t=dijkstra(st,ed);
    cout<< t <<endl;
    return 0;
}

算法3

(spfa) $O(m)$

平均$O(m)$，最坏$O(nm)$

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=3000,M=20000;

int h[N],w[M],e[M],ne[M],idx;
bool ste[N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

int spfa(int st,int ed)
{
    int dist[M];
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    q.push(st);
    dist[st]=0;
    ste[st]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        ste[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!ste[j])
                {
                    ste[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return dist[ed];
}

int main()
{
    int n,m,st,ed;
    cin>>n>>m>>st>>ed;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w),add(b,a,w);
    }
    int t=spfa(st,ed);
    cout<< t <<endl;
    return 0;
}

可自行提交对比时间！