首页 > 代码库 > UVa1599,Ideal Path

UVa1599,Ideal Path

2024-07-14 11:41:31   222人阅读

 
说实话，这题参考的：

http://blog.csdn.net/u013382399/article/details/38227917

倒着BFS就把我难住了T T，原来这样倒着BFS一遍，遍历完所有的点后就能得到每一点到终点的最短距离啊（其实做完反思后仔细想了想，发现其实当第一次bfs到首节点时，该图已经遍历完成了），一开始没转过这个弯来T T，我直接调用了N次dfs（i）囧rz....

一开始我还想着吧color[]排序...这样更费时.....我写的dfs2（）写着写着就乱了，本来思路还清晰，结果越写越乱T T...然后直接看的他的dfs2（）

哎，和人家还有很大差距啊......虽然几乎是直接copy的人家的代码，但是做了深刻的反思，也深度的学习了他的代码与方法，算是学到了一些东西吧， 嘻嘻……至少比自己空领悟节约点时间嘛

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <vector>#include <queue>#define maxn 100000+5using namespace std;vector<int> g[maxn];vector<int> c[maxn];int n,m,vis[maxn],d[maxn],ans[maxn];int init(){    int x,y;    int temp;    memset(vis,0,sizeof(vis));    memset(d,0,sizeof(d));    memset(ans,0,sizeof(ans));      for (int i=0;i<=n;i++)g[i].clear();    for (int i=0;i<=n;i++)c[i].clear();    for (int i=0;i<m;i++){        cin>>x>>y;        g[x].push_back(y);        g[y].push_back(x);        cin>>temp;        c[x].push_back(temp);        c[y].push_back(temp);    }}void bfs1(int n)  {      memset(d,-1,sizeof(d));    queue<int> q;      d[n]=0;      q.push(n);      while(!q.empty())      {          int u=q.front();q.pop();          int sz=g[u].size();          for(int v=0;v<sz;v++)          {              int vv=g[u][v];              if(vv==1)              {                  d[1]=d[u]+1;                  return;              }              if(d[vv]==-1)            {                  d[vv]=d[u]+1;                  q.push(vv);              }          }      }      return;  }  void bfs2()  {      memset(vis,0,sizeof(vis));      queue<int> q;      q.push(1);      while(!q.empty())      {          int u=q.front();q.pop();          if(d[u]==0) return;          int sz=g[u].size();          int mm=-1;          for(int i=0;i<sz;i++)//找到最小的颜色          {              int vv=g[u][i];              if(d[vv]==d[u]-1)              {                  if(mm==-1)                      mm=c[u][i];                  else                      mm=min(mm,c[u][i]);              }          }          int t=d[1]-d[u];          if(ans[t]==0) ans[t]=mm;          else              ans[t]=min(mm,ans[t]);          for(int v=0;v<sz;v++)          {              int vv=g[u][v];              if(vis[vv]==0&&d[vv]==d[u]-1&&c[u][v]==mm)              {                  q.push(vv);                  vis[vv]=1;              }          }      }      return;  }  int main(){    while (cin>>n>>m){        init();        bfs1(n);        bfs2();        printf("%d\n",d[1]);          for(int i=0;i<d[1];i++)          {              if(i) printf(" ");              printf("%d",ans[i]);          }          printf("\n");      }}
View Code

 


联系
我们