图的搜索（与1003类似）
-dfs
#include <iostream> #include <climits> using namespace std; int n,m,s,d,cnt=0; int Dist[500][500]={0}; int Cost[500][500]; int mdist=INT_MAX, mcost=INT_MAX; int path[500]; int mpath[500]; bool visit[500]={0}; void init(){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++) Cost[i][j]=500; } for(int i=1;i<500;i++) path[i]=mpath[i]=-1; path[0]=mpath[0]=s; } void dfs(int a,int b,int dis,int cos){ if(a==b){ if(dis<mdist){ mdist=dis; mcost=cos; for(int i=1;i<=cnt;i++) mpath[i]=path[i]; }else if(dis==mdist){ if(cos<mcost){ mdist=dis; mcost=cos; for(int i=1;i<=cnt;i++) mpath[i]=path[i]; } } return; } if(dis>mdist)return; for(int i=0;i<n;i++) if(a!=i&&Dist[a][i]!=0&&visit[i]==0){ visit[i]=true; path[++cnt]=i; dfs(i,b,dis+Dist[a][i],cos+Cost[a][i]); visit[i]=false; cnt--; } } int main() { int i; cin>>n>>m>>s>>d; init(); i=m; while(i--){ int a,b,c,e; cin>>a>>b>>c>>e; Dist[a][b]=Dist[b][a]=c; Cost[a][b]=Cost[b][a]=e; } visit[s]=true; dfs(s,d,0,0); i=0; while(mpath[i]!=-1){ cout<<mpath[i]<<" "; i++; } cout<<mdist<<" "<<mcost<<endl; return 0; }