Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531471752000,"title":"Travelling","dislikeCnt":1,"content":"```\n#include\u003ciostream\u003e\n#include\u003calgorithm\u003e\n#include\u003ccstdio\u003e\n#include\u003ccmath\u003e\n#include\u003ccstring\u003e\n#include\u003cstring\u003e\nusing namespace std;\nconst int inf\u003d0x7fffffff;\nint d[12],num[60000][12],dp[60000][12],g[20][20],n,m;//g用于记录路径价值,d用于预处理三进制 \nint main(){ //num用于记录每个点被第i次访问的状态 \n d[0]\u003d1; //dp用于记录该点当前在j点,且 \n for(int i\u003d1;i\u003c\u003d11;i++)d[i]\u003dd[i-1]*3;//三进制预处理 \n while(scanf(\"%d%d\",\u0026n,\u0026m)!\u003dEOF){\n for(int i\u003d0;i\u003c\u003dn;i++)\n for(int j\u003d0;j\u003c\u003dn;j++)\n g[i][j]\u003dinf; // 预处理路径价值 \n for(int i\u003d0;i\u003cm;i++){ //记录路径 \n int a,b,w;\n scanf(\"%d%d%d\",\u0026a,\u0026b,\u0026w);\n a--;b--;\n g[a][b]\u003dg[b][a]\u003dmin(w,g[a][b]);\n }\n for(int i\u003d0;i\u003cd[10];i++){ //每个点的状态 ,即第j点在第i次访问时的状态 \n int a\u003di;\n for(int j\u003d0;j\u003c10;j++){\n num[i][j]\u003da%3;\n a/\u003d3;\n }\n }\n for(int i\u003d0;i\u003cd[n];i++) //初始化搜索 \n for(int j\u003d0;j\u003c10;j++)\n dp[i][j]\u003dinf;\n for(int i\u003d0;i\u003cn;i++)dp[d[i]][i]\u003d0; //将起点记作0 \n int ans\u003dinf; //答案初始化 \n for(int i\u003d0;i\u003cd[n];i++){\n int flag\u003d1; \n for(int j\u003d0;j\u003cn;j++){\n if(num[i][j]\u003d\u003d0)flag\u003d0;//此路不通,有无法到达的点 \n if(dp[i][j]\u003d\u003dinf)continue;//不是起点 \n for(int k\u003d0;k\u003cn;k++){\n if(g[j][k]\u003d\u003dinf||num[i][k]\u003d\u003d2)continue;//没有路径或已被访问两次 \n dp[i+d[k]][k]\u003dmin(dp[i+d[k]][k],dp[i][j]+g[j][k]);//取最小值 \n }\n }\n if(flag)//取最小值\n for(int j\u003d0;j\u003cn;j++)\n ans\u003dmin(ans,dp[i][j]);\n }\n if(ans\u003d\u003dinf)ans\u003d-1;\n printf(\"%d\\n\",ans);\n }\n return 0;\n}\n\n```","threadId":31440,"likeCnt":0,"createTime":1531471752000,"isWorkbook":false,"viewCnt":1869,"openness":2,"fav":false,"id":514,"trustable":false}