http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249

题意：出若干个建筑之间的一些路，每条路都有对应的长度和需要的花费，问在保证源点1 到其他个点的距离最短的情况下，最少的花费是多少

题解：最短路

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v,d,c;
int ans,cnt,flag,temp,sum;
int vis[N];
int cost[N];
struct node{
    int v,d,c;
    bool operator<(const node&S)const{
        if(d==S.d)
            return c>S.c;
        return d>S.d;
    }
}s,x,tmp;

priority_queue<node>q;
vector<node>G[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    while(~scanf("%d%d",&n,&m)&&n+m){
        while(!q.empty())
            q.pop();
        memset(vis,0,sizeof(vis));
        memset(cost,0,sizeof(cost));
        for(int i=1;i<=m;i++){
            scanf("%d%d%d%d",&u,&v,&d,&c);
            x.v=v;
            x.c=c;
            x.d=d;
            G[u].push_back(x);
            x.v=u;
            G[v].push_back(x);
        }
        x.v=1;
        x.d=0;
        x.c=0;
        q.push(x);
        while(!q.empty()){
            x=q.top();
            q.pop();
            if(vis[x.v])
                continue;
            vis[x.v]=1;//cout<<x.v<<" "<<x.c<<endl;
            cost[x.v]=x.c;
            for(int i=0,j=G[x.v].size();i<j;i++){
                tmp=G[x.v][i];
                if(vis[tmp.v]==0){
                    tmp.d+=x.d;
                    //tmp.c+=x.c;
                    q.push(tmp);
                }
            }
        }
        ans=0;
        for(int i=1;i<=n;i++)ans+=cost[i],G[i].clear();
        cout<<ans<<endl;
    }

    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4+5,INF=0x3f3f3f3f;
int d[maxn];
int cost[maxn];
bool used[maxn];
int n,m;
struct edge
{
    int to,dis,c;
    edge(){}
    edge(int to,int dis,int c):to(to),dis(dis),c(c){}
};
vector<edge> G[maxn];
void SPFA()
{
    queue<int> que;
    memset(d,INF,sizeof(d));
    memset(used,false,sizeof(used));
    memset(cost,INF,sizeof(cost));
    d[1]=0;
    cost[1]=0;
    used[1]=true;
    que.push(1);
    while(que.size())
    {
        int u=que.front();
        que.pop();
        for(int i=0;i<G[u].size();i++)
        {
            edge e=G[u][i];
            if(d[e.to]>d[u]+e.dis)
            {
                d[e.to]=d[u]+e.dis;
                cost[e.to]=e.c;
                if(!used[e.to])
                {
                    used[e.to]=true;
                    que.push(e.to);
                }
            }
            else if(d[e.to]==d[u]+e.dis&&cost[e.to]>e.c)//可以更新到该点的最小花费
            {
                cost[e.to]=e.c;
                if(!used[e.to])
                {
                    used[e.to]=true;
                    que.push(e.to);
                }
            }
        }
        used[u]=false;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=cost[i];
    cout<<ans<<endl;
}
int main()
{
    while(cin>>n>>m,n||m)
    {
        for(int i=0;i<m;i++)
        {
            int u,v,dis,c;
            cin>>u>>v>>dis>>c;
            G[u].push_back(edge(v,dis,c));
            G[v].push_back(edge(u,dis,c));
        }
        SPFA();
        for(int i=1;i<=n;i++)
            G[i].clear();
    }
    return 0;
}
分类: 图论--最短路