完美公司笔试编程题

#include<bits/stdc++.h> 
using namespace std; 
map<pair<int,int>,int>M; 
map<int,int>dir; 
vector<int>ans; 
set<int>se; 
const int inf=0x7ffffff; 
int s,e; 
void dfs(int x,int sum){ 
  if(x==s) 
      return; 
  for(set<int>::iterator i=se.begin();i!=se.end();i++){ 
      if(sum-M[make_pair(*i,x)]==M[make_pair(s,*i)]){
           dfs(*i,sum-M[make_pair(*i,x)]); break;
       }
    }
    ans.push_back(x);
} 
int main(){ scanf("%d%d",&s,&e); int a,b,c;
     M.clear();
     se.clear();
     dir.clear();
     ans.clear(); 
     while(~scanf("%d%d%d",&a,&b,&c)){
        M[make_pair(a,b)]=c;
        M[make_pair(b,a)]=c;
        se.insert(a);se.insert(b);
     } 
     for(set<int>::iterator i=se.begin();i!=se.end();i++){ 
      for(set<int>::iterator j=se.begin();j!=se.end();j++){ 
        if(M[make_pair(s,*i)]==0)  
                M[make_pair(s,*i)]=inf; 
        if(M[make_pair(s,*j)]==0)  
                M[make_pair(s,*j)]=inf; 
        if(M[make_pair(*j,*i)]==0)  
                M[make_pair(*j,*i)]=inf; 
        if(M[make_pair(s,*i)]>M[make_pair(s,*j)]+M[make_pair(*j,*i)]){
                M[make_pair(s,*i)]=M[make_pair(s,*j)]+M[make_pair(*j,*i)];
         }
       }
     }
     dfs(e,M[make_pair(s,e)]); 
     printf("%d",s); 
     for(int i=0;i<ans.size();i++) 
        printf("->%d",ans[i]); 
     printf("(%d)\n",M[make_pair(s,e)]);
}

全部评论
参考网址在这里 http://blog.csdn.net/yexiaohhjk/article/details/52589368 求指导 急 我不太会 ,只会java 担心人家问我 (太丢人了)。。。。
点赞 回复
分享
发布于 2016-10-15 17:03
我懂了。。。
点赞 回复
分享
发布于 2016-10-16 10:13
英特尔
校招火热招聘中
官网直投

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务