题目：

思路分析：

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

多几个限制条件而已

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

代码实现：

/*
*@Author:   GuoJinlong
*@Language: C++
*/
//#include 
/**                                                     __----~~~~~~~~~~~------___*                                    .  .   ~~//====......          __--~ ~~*                    -.            \_|//     |||\\  ~~~~~~::::... /~*                 ___-==_       _-~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;
mapmp;
mapmp1;
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]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]>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();vectorp;int x=mp[en];while (x!=-1) {p.push_back(mp1[x]);x=pre[x];}
//    cout<"<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！