团体程序设计天梯赛(L3-011 直捣黄龙 (30 分))_天梯赛直捣黄龙c语言

题目：

思路分析：

一个多条件的最短路模型（魔改dij就行

多几个限制条件而已

发现pta上面都是dij的模型 来几个堆优化的题目也算呀！ 

代码实现：

/*
*@Author:   GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
 *                                                     __----~~~~~~~~~~~------___
 *                                    .  .   ~~//====......          __--~ ~~
 *                    -.            \_|//     |||\\  ~~~~~~::::... /~
 *                 ___-==_       _-~o~  \/    |||  \\            _/~~-
 *         __---~~~.==~||\=_    -_--~/_-~|-   |\\   \\        _/~
 *     _-~~     .=~    |  \\-_    '-~7  /-   /  ||    \      /
 *   .~       .~       |   \\ -_    /  /-   /   ||      \   /
 *  /  ____  /         |     \\ ~-_/  /|- _/   .||       \ /
 *  |~~    ~~|--~~~~--_ \     ~==-/   | \~--===~~        .\
 *           '         ~-|      /|    |-~\~~       __--~~
 *                       |-~~-_/ |    |   ~\_   _-~            /\
 *                            /  \     \__   \/~                \__
 *                        _--~ _/ | .-~~____--~-/                  ~~==.
 *                       ((->/~   '.|||' -_|    ~~-/ ,              . _||
 *                                  -_     ~\      ~~---l__i__i__i--~~_/
 *                                  _-~-__   ~)  \--______________--~~
 *                                //.-~~~-~_--~- |-------~~~~~~~~
 *                                       //.-~~~--\
 *                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 *                               神兽保佑            永无BUG
 */
 
const int MAX=1001;
int vis[MAX];
int dis[MAX][MAX];
int di[MAX];
int diss[MAX];
int point[MAX];
int pre[MAX];
int path[MAX];
int a[MAX];
int n,k;
map<string,int>mp;
map<int,string>mp1;
void dij(){
    mms(vis,0);
    mms(pre,-1);
    mms(diss,INF);
    diss[1]=0;
    di[1]=0;
    point[1]=0;
    path[1]=1;
    for(int i=1;i<=n;i++){
        int v=-1;
        int m1=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&diss[j]<m1){
                m1=diss[j];
                v=j;
            }
        }
        vis[v]=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                if(diss[j]>diss[v]+dis[v][j]){
                    diss[j]=diss[v]+dis[v][j];
                    path[j]=path[v];
                    pre[j]=v;
                    di[j]=di[v]+a[j];
                    point[j]=point[v]+1;
                }
                else if(diss[j]==diss[v]+dis[v][j]){
                    path[j]+=path[v];
                    if(point[j]<point[v]+1){
                        point[j]=point[v]+1;
                        di[j]=di[v]+a[j];
                        pre[j]=v;
                    }
                    else if(point[j]==point[v]+1){
                        if(di[j]<di[v]+a[j]){
                            di[j]=di[v]+a[j];
                            pre[j]=v;
                            
                        }
                    }
                }
            }
        }
    }
}
int main(){
    string st,en;
    mms(dis,INF);
    cin>>n>>k>>st>>en;
    int num=1;
    mp[st]=num++;
    mp1[1]=st;
    for(int i=1;i<=n-1;i++){
        string s;
        int x;
        cin>>s>>x;
        mp[s]=num++;
        mp1[mp[s]]=s;
        a[mp[s]]=x;
    }
    while (k--) {
        string a,b;
        int x;
        cin>>a>>b>>x;
        int x1=mp[a];
        int x2=mp[b];
        dis[x1][x2]=x;
        dis[x2][x1]=x;
    }
    dij();
    vector<string>p;
    int x=mp[en];
    while (x!=-1) {
        p.push_back(mp1[x]);
        x=pre[x];
    }
//    cout<<p.size();
    reverse(p.begin(),p.end());
    for(int i=0;i<p.size();i++){
        if(i==0)cout<<p[i];
        else cout<<"->"<<p[i];
    }
    cout<<endl;
    x=mp[en];
    cout<<path[x]<<" "<<diss[x]<<" "<<di[x];
}