网站改版索引量下降,网站开发公司更换,潍坊小企业网站建设,wap手机#xff08;这题基本上把最短路能求的都求了个遍#xff0c;除了麻烦一点#xff0c;难度其实还好#xff09;
#xff08;卡题原因#xff1a;dijks漏了对路径条数的初始化。#xff09;
#includebits/stdc.h
using namespace std;
#define int long long
i…这题基本上把最短路能求的都求了个遍除了麻烦一点难度其实还好
卡题原因dijks漏了对路径条数的初始化。
#includebits/stdc.h
using namespace std;
#define int long long
int n,k;
string st,ed;
mapstring,intmp;
mapint,stringname;
mapint,intw;
int e[210][210];
int indx0;
int getID(string s){if(mp.count(s)){return mp[s];}name[indx]s;mp[s]indx;return mp[s];
}
int dist[210];
int hap[210],num[210];
int sum[210];
int p[210];
bool vis[210];
void dijks(int u){memset(dist,0x3f,sizeof dist);memset(vis,0,sizeof vis);memset(p,-1,sizeof p);dist[u]0;sum[u]1;//记得每个都要初始化漏了这个结果debug半多小时for(int i0;iindx;i){u-1;int miINT_MAX;for(int j0;jindx;j){if(!vis[j]midist[j]){uj;midist[j];}}if(u-1)break;vis[u]1;for(int j0;jindx;j){if(!vis[j]){if(dist[j]dist[u]e[u][j]){sum[j]sum[u]sum[j];if(hap[j]hap[u]w[j]){if(num[j]num[u]1){p[j]u;num[j]num[u]1;}}else if(hap[j]hap[u]w[j]){p[j]u;hap[j]hap[u]w[j];num[j]num[u]1;}}else if(dist[j]dist[u]e[u][j]){sum[j]sum[u];p[j]u;dist[j]dist[u]e[u][j];hap[j]hap[u]w[j];num[j]num[u]1;}}}}ugetID(ed);coutsum[u] dist[u] hap[u] (hap[u])/num[u]endl;
}
int flag0;
void dfs(int u){if(u-1)return ;dfs(p[u]);if(flag)cout-;coutname[u];flag1;
}
signed main(){cinnkst;memset(e,0x3f,sizeof e);edROM;getID(st);getID(ed);for(int i0;in-1;i){string city;cincity;int d;cind;w[getID(city)]d;// coutgetID(city) ;}w[getID(st)]0;for(int i0;ik;i){string c1,c2;cinc1c2;int a,b,d;cind;agetID(c1);bgetID(c2);e[a][b]e[b][a]d;}dijks(getID(st));dfs(getID(ed));
}
