dijkstra模板题
问题的关键在于不同情况的判断
相等的时候会改变哪些值
最短的时候更新哪些值
代码量基本90-150行了很难优化
见注释
#include <bits/stdc++.h>
using namespace std;
#define MAXN 0X3F3F3F3F
int graph[500][500];
map<string, int> happy;//某个城市的快乐值
map<int, string> rev;//反向查找
map<string, int> id;
int path[500];//保存路径
int vis[500];//是否访问
int spend[500];//到该点的开销
int happiness[500];//到该点的快乐程度
int route[500];//经过的路线条数
int num[500];//经过的顶点个数
int N,K;
void dijkstra(){//初始化部分for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){graph[i][j]=MAXN;}spend[i]=MAXN;//初始花费无穷大}for(int i=1;i<=K;i++){
//根据映射修改邻接表string a,b;int q;cin>>a>>b>>q;graph[id[a]][id[b]]=graph[id[b]][id[a]]=q;}spend[1]=0;//起点花费=0path[1]=-1;//起点之前没有其他点了route[1]=1;//路线为1条num[1]=1;//一个顶点for(int i=1;i<N;i++){
//dijkstra核心部分int mmin=MAXN;//初始化最小值int v;for(int j=1;j<=N;j++){
//找到花销最小的点if(!vis[j]){if(spend[j]<mmin){mmin=spend[j];v=j;}}}vis[v]=1;//访问for(int j=1;j<=N;j++){
//访问他的邻接点if(!vis[j]&&graph[v][j]!=MAXN){
//可到达并且没有访问if(spend[v]+graph[v][j]<spend[j]){
//更新最值spend[j]=spend[v]+graph[v][j];happiness[j]=happiness[v]+happy[rev[j]];//最短路径，叠加快乐值num[j]=num[v]+1;//顶点个数++route[j]=route[v];//路线沿用他的path[j]=v;//保存路径}else if(spend[j]==spend[v]+graph[v][j]){
//花销一样route[j]+=route[v];//路线加上新增的if(happiness[j]<happiness[v]+happy[rev[j]]){
//由于是花销一样的，看快乐程度 取大的快乐程度happiness[j]=happiness[v]+happy[rev[j]];num[j]=num[v]+1;//节点++path[j]=v;//保存路径}else if(happiness[j]==happiness[v]+happy[rev[j]]){
//快乐程度一样if(num[j]>num[v]+1){
//用节点数更少的num[j]=num[v]+1;path[j]=v;//保存路径}}}} }}
}
void print(int t){if(t==1){printf("%s",rev[1].c_str());return;}print(path[t]);printf("->%s",rev[t].c_str() );
}
int main(){cin>>N>>K;string start;cin>>start;id[start]=1;//开始点为1rev[1]=start;for(int i=2;i<=N;i++){string temp;int cost;cin>>temp>>cost;happy[temp]=cost;//某点的快乐程度id[temp]=i;//对应关系表rev[i]=temp;//反向对应}dijkstra();printf("%d %d %d %d\n",route[id["ROM"]],spend[id["ROM"]],happiness[id["ROM"]], happiness[id["ROM"]]/(-1+num[id["ROM"]]));print(id["ROM"]);//递归倒序输出return 0;
}