C - 畅通工程续

这个题目嘛就是求最短路径咯,比赛的时候想的是Dij,然后用了邻接矩阵过的。效率比较低。而且比赛的时候换了好几种算法都是错的,一定要注意边界值的问题!!!下面贴出比赛时的代码,和后来的两段优化代码。


题目:飞机票直达(C - 畅通工程续


1、Dijkstra+邻接矩阵

Memory: 1964 KB
Time: 46 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=200+5;
const int inf=999999;
int n, m, a, b, x, s, t, i, j;
int dist[maxn][maxn], flag[maxn], dis[maxn];
void Init()
{
    memset(flag, 0, sizeof(flag));
    for(i=0;i<maxn;i++)dis[i]=-1;
    for(i=0;i<maxn;i++)for(j=0;j<maxn;j++)
    {
        if(i==j)dist[i][j]=0;
        else dist[i][j]=inf;
    }
    for(i=0;i<m;i++)
    {
        cin>>a>>b>>x;
        if(dist[a][b]>x)dist[a][b]=dist[b][a]=x;
    }
    cin>>s>>t;
}
void Dij()
{
    dis[s]=0;
    for(i=1;i<=n;i++)
    {
        int tmin=inf, cur;
        for(j=0;j<n;j++)
        {
            if(!flag[j]&&(dis[j]!=-1&&dis[j]<tmin))
            {
                tmin=dis[j];
                cur=j;
            }
        }
        flag[cur]=1;
        for(j=0;j<n;j++)
        {
            if(!flag[j]&&dist[cur][j]<inf&&(dis[j]==-1||dis[j]>dis[cur]+dist[cur][j]))
                dis[j]=dis[cur]+dist[cur][j];
        }
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(cin>>n>>m)
    {
        Init();
        Dij();
        cout<<dis[t]<<endl;
    }
    return 0;
}


2、优先队列的Dijkstra+邻接表

Memory: 1768 KB
Time: 15 MS
Language: C++
Result: Accepted
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=200+5;
const int inf=999999;
int n, m, s, t;
vector<pair<int, int> >Node[maxn];
priority_queue<pair<int, int > > Q;
int dis[maxn];
void Init()
{
    int a, b, x;
    for(int i=0;i<maxn;i++)
    {
        Node[i].clear();
        dis[i]=inf;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d", &a,&b,&x);
        Node[a].push_back(make_pair(b, x));
        Node[b].push_back(make_pair(a, x));
    }
    scanf("%d%d", &s, &t);
    dis[s]=0;
    Q.push(make_pair(-dis[s], s));
}
void Dijkstra()
{
    while(!Q.empty())
    {
        int u=Q.top().second;
        Q.pop();
        for(int i=0;i<Node[u].size();i++)
        {
            int v=Node[u][i].first;
            if(dis[v]>dis[u]+Node[u][i].second)
            {
                dis[v]=dis[u]+Node[u][i].second;
                Q.push(make_pair(-dis[v], v));
            }
        }
    }
}
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        Init();
        Dijkstra();
        if(dis[t]==inf)printf("-1\n");
        else printf("%d\n", dis[t]);
    }
    return 0;
}


3、Spfa算法


Memory: 1764 KB
Time: 0 MS
Language: C++
Result: Accepted
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=200+5;
const int inf=999999;
int n, m, s, t;
vector<pair<int, int> >Node[maxn];
queue<int> Q;
int dis[maxn], inq[maxn];
void Init()
{
    int a, b, x;
    for(int i=0;i<maxn;i++)
    {
        Node[i].clear();
        inq[i]=0;
        dis[i]=inf;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d", &a,&b,&x);
        Node[a].push_back(make_pair(b, x));
        Node[b].push_back(make_pair(a, x));
    }
    scanf("%d%d", &s, &t);
    Q.push(s);
    dis[s]=0;
    inq[s]=1;
}
void Spfa()
{
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        inq[u]=0;
        for(int i=0;i<Node[u].size();i++)
        {
            int v=Node[u][i].first;
            if(dis[v]>dis[u]+Node[u][i].second)
            {
                dis[v]=dis[u]+Node[u][i].second;
                if(inq[v]==1)continue;
                Q.push(v);
            }
        }
    }
}
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        Init();
        Spfa();
        if(dis[t]==inf)printf("-1\n");
        else printf("%d\n", dis[t]);
    }
    return 0;
}