学校网站建设团队,宁波公司,wordpress新闻类主题,网站建设 媒体广告1.dijkstra维护最长路 下面这个是讨论区的一个佬的理解#xff0c;非常的nice 总结一句话#xff0c;dijkstra的贪心保证了每次选定的点在之后都不会被其他点所更新了
同理维护最长路的时候我们发现#xff0c;如果权值是0-1的话#xff0c;选定的最大值在之后不会变的更大…1.dijkstra维护最长路 下面这个是讨论区的一个佬的理解非常的nice 总结一句话dijkstra的贪心保证了每次选定的点在之后都不会被其他点所更新了
同理维护最长路的时候我们发现如果权值是0-1的话选定的最大值在之后不会变的更大
所以可以用dijkstra来维护最长路
#includebits/stdc.h
using namespace std;
const int N 1e510;
double g[2010][2010];
int n,m,s,t;
double dist[N];
bool st[N];
double dijkstra()
{dist[s] 1.0;for(int i1;in;i){int t -1;for(int j1;jn;j)if(!st[j](t-1||dist[j]dist[t]))t j;st[t] 1;for(int j1;jn;j)if(dist[j]dist[t]*g[t][j])dist[j] dist[t]*g[t][j];}return dist[t];
}int main()
{cinnm;for(int i1;im;i){int a,b,c;cinabc;double z (100.0-c*1.0)/100.0;g[a][b] g[b][a] max(g[a][b],z);}cinst;printf(%.8lf,100.0/dijkstra()*1.0);} 2.stringstream处理不定长输入 #includebits/stdc.h
using namespace std;
int n,m;
const int N 1100;
int g[N][N];
int dist[N];
int a[N];
bool st[N];void dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1] 0;for(int i1;in;i){int t -1;for(int j1;jn;j)if(!st[j](t-1||dist[j]dist[t]))t j;st[t] 1;for(int j1;jn;j)if(dist[j]dist[t]g[t][j])dist[j] dist[t] g[t][j];}
}int main()
{cinmn;memset(g,0x3f,sizeof g);for(int i1;in;i)g[i][i] 0;getchar();for(int i1;im;i){string str;getline(cin,str);stringstream ssin(str);int k 1;while(ssina[k])k;k--;for(int s1;sk;s)for(int j1;js;j)g[a[j]][a[s]] 1;}dijkstra();if(dist[n]0x3f3f3f3f)coutNO;else coutdist[n]-1;} 3.简单虚拟原点 注意酋长不一定是这里面等级最高的 所以我们要枚举区间算好几次dijkstra
#includeiostream
#includecstring
using namespace std;const int N 1010;
int g[N][N];
int dist[N];
bool st[N];
int m,n;
int level[N];int dijkstra(int l,int r){memset(dist,0x3f,sizeof dist);dist[0] 0;memset(st,0,sizeof st);for(int i1;in;i){int t -1;for(int j0;jn;j)if(!st[j](t-1||dist[j]dist[t]))t j;st[t] 1;for(int j1;jn;j)if(level[j]llevel[j]r)dist[j] min(dist[j],dist[t]g[t][j]);}return dist[1];
}int main()
{cinmn;memset(g,0x3f,sizeof g);for(int i0;in;i)g[i][i] 0;for(int i1;in;i){int p,l,x;cinplx;level[i] l;g[0][i] p;for(int j1;jx;j){int a,b;cinab;g[a][i] min(g[a][i],b);}}int res 0x3f3f3f3f;for(int ilevel[1]-m;ilevel[1];i)res min(res,dijkstra(i,im));coutres;}
