链接:hdu 1535

题意：有编号1～P的站点， 有Q条公交车路线，公交车路线只从一个起点站直接到达终点站，是单向的，每条路线有它自己的车费。有P个志愿者早上从1站点出发，每个人要到达一个不同公交站点，（即一个站点有一个人）然后到了晚上再返回点1。求所有人来回的最小费用之和。

分析：去的费用是从1站点出发的总和，直接正向建图

      回来的费用是从各站点返回的到1站点的费用总和，如果一个一个求，会超时，所以要反向建图

注意：以为题目数据较大，二维数组开不了那么大，并且如果每次循环找与某点相连的边，也会超时，

可以用 结构体+排序 加以优化，或者用邻接表

dijkstra+结构体（2093MS）

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#define N 1000000
using namespace std;
struct stu
{
    int a,b,c;
}s[N+10];
int a[N+10],b[N+10],c[N+10],n,m,k;
int dis[N+10],vis[N+10],next[N+10];
int cmp(struct stu x,struct stu y)
{
    return x.a<y.a;
}
void dijkstra(int pos)
{
    int i,j,min;
    for(i=1;i<=n;i++)
        dis[i]=INT_MAX;
    memset(vis,0,sizeof(vis));
    vis[pos]=1;
    for(i=next[pos];i<=m;i++){
        if(s[i].a!=pos)
            break;
        dis[s[i].b]=s[i].c;
    }
    dis[pos]=0;
    for(i=1;i<n;i++){
        min=INT_MAX;
        for(j=1;j<=n;j++)
            if(!vis[j]&&dis[j]<min){
                min=dis[j];
                pos=j;
            }
        vis[pos]=1;
        for(j=next[pos];j<=m;j++){
            if(s[j].a!=pos)
                break;
            if(!vis[s[j].b]&&dis[pos]+s[j].c<dis[s[j].b])
                dis[s[j].b]=dis[pos]+s[j].c;
        }
    }
}
void jiantu(int *a,int *b,int *c)
{
    int i,k=1;
    for(i=1;i<=m;i++){
        s[k].a=a[i];
        s[k].b=b[i];
        s[k++].c=c[i];
    }
    sort(s+1,s+k,cmp);          //排序后相同起点的边会在一起
    memset(next,0,sizeof(next));
    next[s[1].a]=1;
    for(i=2;i<=m;i++){
        if(s[i].a!=s[i-1].a)
            next[s[i].a]=i;
    }
}
int main()
{
    int T,i,sum;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        jiantu(a,b,c);
        dijkstra(1);
        sum=0;
        for(i=2;i<=n;i++)
            sum+=dis[i];
        jiantu(b,a,c);         //反向建图
        dijkstra(1);
        for(i=2;i<=n;i++)
            sum+=dis[i];
        printf("%d\n",sum);
    }
    return 0;
}

dijkstra+邻接表 （1312MS）

#include<stdio.h>
#include<string.h>
#include<limits.h>
#define N 1000000
int a[N+10],b[N+10],c[N+10],n,m;
int dis[N+10],vis[N+10],first[N+10],next[N+10];
void dijkstra(int pos,int *a,int *b,int *c)
{
    int i,j,min;
    for(i=1;i<=n;i++)
        dis[i]=INT_MAX;
    memset(vis,0,sizeof(vis));
    vis[pos]=1;
    i=first[pos];
    while(i!=-1){
        dis[b[i]]=c[i];
        i=next[i];
    }
    dis[pos]=0;
    for(i=1;i<n;i++){
        min=INT_MAX;
        for(j=1;j<=n;j++)
            if(!vis[j]&&dis[j]<min){
                min=dis[j];
                pos=j;
            }
        vis[pos]=1;
        j=first[pos];
        while(j!=-1){
            if(!vis[b[j]]&&dis[pos]+c[j]<dis[b[j]])
                dis[b[j]]=dis[pos]+c[j];
            j=next[j];
        }
    }
}
void jiantu(int *a,int *b,int *c)
{
    int i;
    memset(first,-1,sizeof(first));
    for(i=1;i<=m;i++){
        next[i]=first[a[i]];
        first[a[i]]=i;
    }
}
int main()
{
    int T,i,sum;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        jiantu(a,b,c);
        dijkstra(1,a,b,c);
        sum=0;
        for(i=2;i<=n;i++)
            sum+=dis[i];
        jiantu(b,a,c);          //反向建图
        dijkstra(1,b,a,c);      //记得传数组也得反向
        for(i=2;i<=n;i++)
            sum+=dis[i];
        printf("%d\n",sum);
    }
    return 0;
}

SPFA+结构体 （1359MS）

#include<stdio.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<queue>
#define MAXN 1000000
using namespace std;
struct e
{
    int begin;
    int end;
    int dis;
} edge1[MAXN+10],edge2[MAXN+10];
int dis[MAXN+10],first[MAXN+10];
bool vis[MAXN+10];
int T,S,D,N,k,M;
void SPFA(int begin,struct e edge[])
{
    for (int i=1; i<=N; i++)
    {
        dis[i]=INT_MAX;
        vis[i]=0;
    }
    queue <int> Q;
    Q.push(begin);
    dis[begin]=0;
    while (!Q.empty())
    {
        begin=Q.front();
        Q.pop();
        vis[begin]=0;
        for (int i=first[begin]; edge[i].begin==begin; i++) //可以只遍历begin==edge[i].begin的edge
            if (dis[edge[i].end]>dis[begin]+edge[i].dis)
            {
                dis[edge[i].end]=dis[begin]+edge[i].dis;
                if (!vis[edge[i].end])
                {
                    Q.push(edge[i].end);
                    vis[edge[i].end]=1;
                }
            }
    }
}
void init(struct e edge[]) //first存各个顶点作为结点时的第一个下标
{
    memset(first,0,sizeof(first));
    first[edge[1].begin]=1;
    for (int i=2;i<=M;i++)
        if (edge[i-1].begin!=edge[i].begin) first[edge[i].begin]=i;
}
bool cmp(struct e a,struct e b)
{
    return a.begin<b.begin;
}
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        scanf("%d %d",&N,&M);
        int x1,x2,x3;
        for (int i=1; i<=M; i++)
        {
            scanf("%d %d %d",&x1,&x2,&x3); //cin跑了2600ms scanf只要1300ms
            //cin>>x1>>x2>>x3;
            edge1[i].begin=x1,edge1[i].end=x2,edge1[i].dis=x3;
            edge2[i].begin=x2,edge2[i].end=x1,edge2[i].dis=x3;
        }
        sort(edge1+1,edge1+M+1,cmp); //按begin顶点排序
        sort(edge2+1,edge2+M+1,cmp);
        init(edge1);
        SPFA(1,edge1);
        int cnt=0;
        for (int i=1; i<=N; i++)
            cnt+=dis[i];
        init(edge2);
        SPFA(1,edge2);
        for (int i=1; i<=N; i++)
            cnt+=dis[i];
        printf("%d\n",cnt);
    }
    return 0;
}